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.

Expert Solution

Colby Messinger answered 2 years ago

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.

Let G be any context-free grammar. Show that the number of strings that have a derivation...

Let G be any context-free grammar. Show that the number of strings that have a derivation in G of length n or less, for any n > 0, is finite. Could you please answer with clear explanation. The question is from Elaine Rich's Automata, Computability and Complexity Chapter 11 Exercise 14.

convert the following grammar to Chomsky Normal Form S -> D0S1 | 1 D -> F0D1...

convert the following grammar to Chomsky Normal Form S -> D0S1 | 1 D -> F0D1 | 0 | e | FG F -> SF | DD | S G -> GK | DG

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.

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.

What makes a deterministic context free grammar deterministic?

Theory of Computation Problem Let G be an arbitrary CFG (Context-free Grammer), and let DG be...

Theory of Computation Problem Let G be an arbitrary CFG (Context-free Grammer), and let DG be the string-pushing PDA(pushdown automata) for it. Let w be some string of length n in L(G). Suppose you know that the leftmost derivation of w in G consists of m substitutions. How many transitions would be in the corresponding computation of DG for input string w? Justify your answer carefully.

Consider the following context-free grammar G: E ® T + E ® * T i E...

Consider the following context-free grammar G: E ® T + E ® * T i E ® f i E ® * f + T ® + Questions: (5 points) Compute the Canonical LR(1) Closure set for state I0 for grammar G. (10 points) Compute (draw) the DFA that recognizes the Canonical LR(1) sets of items for grammar G. (5 points) Construct the corresponding Canonical LR(1) parsing table. (10 points) Compute (draw) the DFA for LALR(1). (5 points) Construct LALR(1)...

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)...

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.

Question