Question

In: Computer Science

(a) How Context Free languages are different from Regular languages. (b) What are the automata accepting...

(a) How Context Free languages are different from Regular languages. (b) What are the automata accepting those languages and how they are different from DFA and NFA. (c) How the grammar of Context Free Languages looks different from those in Regular languages.

Solutions

Expert Solution

(a)Regular languages are lanuages generated by a Regular Grammar.Regular languages can be of finite length or non-finite length.In case of non-finite, it has a pattern which will satisfy pumping lemma for Regular languages.
Comtext Free languages are lanuages generated by a Context free Grammar.Context free laguages are super set of Regular language.
It may or may not statisfy pumping lemma for Regular languages. But it will satisfy pumping lemma for Context free languages.

(b)Regular languages accepted by Finite Automata, while context free languages accepted by Push down Automata(PDA).
PDA needs a memory unit(stack),while DFA and NFA do not have any memory unit.

(c)Regular grammar can be right or left linear,while context free grammar is combination of terminals and non-terminals.
Regular grammars are non-ambiguous, there is only one production rule for a given non-terminal, while there can be more than one in the case of a context-free grammar.

venereology answered 1 year ago
Next > < Previous

Related Solutions

Prove that all regular languages are context free. Note: Proof must proceed by structural induction on...
Prove that all regular languages are context free. Note: Proof must proceed by structural induction on regular expressions Please prove by Structural Induction. Will Upvote for correct answer. Thanks
Closure under Context-Free Languages Show that the following operations are closed under context-free languages: union concatentation...
Closure under Context-Free Languages Show that the following operations are closed under context-free languages: union concatentation Kleene star
Prove the following Closure Properties with respect to Context Free Languages. 1. Show that Context Free...
Prove the following Closure Properties with respect to Context Free Languages. 1. Show that Context Free Languages are Closed under union(∪), concatenation(·), kleene star(*). (Hint: If L1 and L2 are Context Free languages then write Context Free grammar equivalent to L1 ∪ L2, L1 · L2, L∗ 1 ) 2. Show that if L1 and L2 are Context Free Languages, then L1 ∩ L2 is not necessarily Context Free. (Hint: Use Proof by Counter Example)
Are the following languages over {a, b} regular? If they are then prove it. If they...
Are the following languages over {a, b} regular? If they are then prove it. If they are not prove it with the Pumping Lemma a) {ap | p is a prime number} b) {xax | x Î{a,b}*} (start by listing some strings in, not in, the language
Regular => Context-Free Give a proof by induction on regular expressions that: For any language A,...
Regular => Context-Free Give a proof by induction on regular expressions that: For any language A, if A is regular, then A is also context-free. You may assume that the statements from the previous Closure under Context-Free Languages problem are proved. R is a regular expression if RR is: a for some a∈alphabet Σ, the empty string ε, the empty set ∅, R​1​​∪R​2​​, sometimes written R​1​​∣R​2​​, where R​1​​ and R​2​​ are regular expressions, R​1​​∘R​2​​, sometimes written R​1​​R​2​​, where R​1​​ and...
5 Regular => Context-Free Give a proof by induction on regular expressions that: For any language...
5 Regular => Context-Free Give a proof by induction on regular expressions that: For any language A, if A is regular, then A is also context-free. You may assume that the statements from the previous Closure under Context-Free Languages problem are proved.
explain in an paragraph what is microfinance and how it is different from regular finance ,...
explain in an paragraph what is microfinance and how it is different from regular finance , describe in detail of all the differences. how can microfinance help eradicate poverty? Is microfinance sustainable? what kind of projects can develop drom microfinance?
9. Explain how Conway’s Life works in the context of cellular automata. Describe the update rules...
9. Explain how Conway’s Life works in the context of cellular automata. Describe the update rules of the Game of Life. 10. Explain how genetic programming can be used to solve problems.
Give context free grammars for the languages below. To avoid mistakes, I recommend using scratch paper...
Give context free grammars for the languages below. To avoid mistakes, I recommend using scratch paper to check that your grammars produce the right set of string. This question is structured so that nonterminals (and associated rules) from an earlier subquestion might be useful in a grammar for a later sub-question. That’s why, rather than “S” as the start symbol, we will used different start symbols for each part. If you do use a nonterminal from an earlier sub-question, say...
Give context free grammars for the languages below. To avoid mistakes, I recommend using scratch paper...
Give context free grammars for the languages below. To avoid mistakes, I recommend using scratch paper to check that your grammars produce the right set of string. This question is structured so that nonterminals (and associated rules) from an earlier subquestion might be useful in a grammar for a later sub-question. That’s why, rather than “S” as the start symbol, we will used different start symbols for each part. If you do use a nonterminal from an earlier sub-question, say...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT