For a grammar G with the productions where G = ( {S, A, B}, {a, b},...

For a grammar G with the productions where G = ( {S, A, B}, {a, b}, S, P ) with productions

S --> AB | bbbB, A --> b | Ab, B --> a..

1.Show that the grammar G is ambiguous.

2.Give language L that is generated by G, L = L(G), in a formal expression (including a regular expression).

3.Can you construct an unambiguous grammar that is equivalent to G? Otherwise, show that G is inherently ambiguous.

Solutions

Expert Solution

Ambiguity is verified by checking the leftmost derivation trees or parse trees , if for a string parse trees are more than one then it is ambiguous grammar.

So by substitution of A production into S...the ambiguity of string parse trees are removed.

Kindly comment for queries if any, upvote if you like it.

Thankyou.

venereology answered 1 year ago

Next > < Previous

Related Solutions

Consider the context-free grammar G = ( {S}, {a, b}, S, P) where P = {...

Consider the context-free grammar G = ( {S}, {a, b}, S, P) where P = { S -> aaSb | aab }. Construct a NPDA M that such that L(M) = L(G). I would like the transition graph for this NPDA please.

Given a grammar G, G = (Ν, Σ, Π, S), where Ν = { ... }...

Given a grammar G, G = (Ν, Σ, Π, S), where Ν = { ... } Σ = { ... } Π = { ... } S is ... For a string ... write (a) A leftmost derivation (b) A rightmost derivation

Simplify the grammar G. Does L(G) contain ε ? S -> A B C | B...

1. Consider the regular grammar G given below: S → aS|aA|bB|λ A → aA|bS B →...

1. Consider the regular grammar G given below: S → aS|aA|bB|λ A → aA|bS B → bB|aS (a) Give a derivation for the strings aabbba and baaba (b) Give an infinite language L such that L is not a subset of L(G) (c) Give a regular expression that describes the language L(G).

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.

Now that you know a bit about BNF's, try writing a grammar (productions) for the "language"...

Now that you know a bit about BNF's, try writing a grammar (productions) for the "language" of a phone number, which consists of: three digits enclosed in parentheses - the first digit cannot be "0" (zero) followed by three digits - the first digit cannot be "0" (zero) followed by a "-" (dash) followed by four digits So, (757)530-4601 is a valid phone number. All the following numbers are invalidaccording to this grammar: 757-530-4601 (area code is not in parentheses)...

Write down a Context Free Grammar with 8 productions including 4 variables and 3 terminals. i....

Write down a Context Free Grammar with 8 productions including 4 variables and 3 terminals. i. Check whether the Context Free Grammar is ambiguous or not. Justify your answer with necessary example. ii. Finally, construct the reduced grammar corresponding to your generated grammar.

Question