Question

In: Computer Science

For each of the following grammars, first classify the grammar as Regular, Linear, Context-Free or Context-Sensitive,...

For each of the following grammars, first classify the grammar as Regular, Linear, Context-Free or Context-Sensitive, and then precisely describe the language generated by the grammar.

(1) S → aRa

R → aR | bR | є

(2) S → A | B

A → aaaA | є

B → Bbb | b

(3) S → RbR

R → aRb | bRa | RR | bR | є

(4)   S → aSbSaS | aSaSbS | bSaSaS | є

   (5) S → a S b | C  

Set of terminals here is T = {a, b, c}     

C → cc C | є

Solutions

Expert Solution

Hope I helped you.

venereology answered 4 months ago
Next > < Previous

Related Solutions

This project is intended to increase your understanding of languages and grammars. In a regular grammar...
This project is intended to increase your understanding of languages and grammars. In a regular grammar (RG), all production rules must have one of the following forms:                         Ni = t1t2t3...tkNj Ni = t1t2t3...tk where ti denotes a terminal (alphabet symbol), and Nj and Nj denote nonterminals. Any language defined by a regular grammar is a regular language. Regular languages can also be defined by finite automata, transition graphs, and regular expressions. More complex grammars, such as context-free grammars (CFG),...
1. regular expressions as a mechanism to specify tokens, 2. defining context-free grammars for language constructs,...
1. regular expressions as a mechanism to specify tokens, 2. defining context-free grammars for language constructs, and 3. derivation of language terms and expressions based on a context-free grammar. 1 Regex 1. Define the regex for the following description of tokens: (a) Any string that starts with character t (b) Any string of at least length 3 that starts with t and ends with u (c) Any string that specifies the range of numbers between 11 and 23. (d) Any...
What makes a deterministic context free grammar deterministic?
What makes a deterministic context free grammar deterministic?
Let G = (AN , AT , S, P) be a context-free grammar in Chomsky normal...
Let G = (AN , AT , S, P) be a context-free grammar in Chomsky normal form. Prove that if there exists a word w ∈ L(G) generated by a derivation that uses more than |P| + |AT | steps, then L(G) is infinite.
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...
Prove that if G is a context-free grammar in which every variable occurs on the left...
Prove that if G is a context-free grammar in which every variable occurs on the left side of at most one production, then G is unambiguous.
Find Consider the following context-free grammar G: S --> T#T T --> C A --> aA...
Find Consider the following context-free grammar G: S --> T#T T --> C A --> aA | epsilon B --> bB | epsilon C --> cC C --> c a) Give the set of unproductive symbols in G? b) Give an equivalent grammar without useless symbols.
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.
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