Let G be a context-free grammar in Chomsky normal form that contains b

Back to the 2021 paper

Module 2: Context-free languages and pushdown automata

20217m

Let $G$ be a context-free grammar in Chomsky normal form that contains $b$ variable. Show that if $G$ generates some string using a derivation with at least $2^b$ steps, then $L(G)$ is infinite.

Search Google Ask AI

Similar questions

FORMAL LANGUAGE & AUTOMATA THEORYLet G be a CFG in CNF with b variables. Show that if G derives any string using at least 2^b steps, then L(G) is infinite.20217m Formal Language & Automata TheoryProve that if L is the language generated by an unrestricted grammar G = (N, T, P, S), then L is recognized by a turing machine.20207m FORMAL LANGUAGE & AUTOMATA THEORYDiscuss the Chomsky hierarchy of grammars with suitable examples.20237m Formal Language & Automata TheoryConsider the following statements about the context-free grammar: (1) G = \{S \to SS, S \to ab, S \to ba, S \to \epsilon\} (2) G is ambiguous (3) G produces all strings with equal number of a's and b's G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G? (i) 1 only (ii) 1 and 3 (iii) 2 and 3 (iv) 1, 2 and 320192m

PreviousShow that the language L = \{a^{n!} : n \ge 0\} is not regular or not context-free language.NextState and prove pumping lemma for regular sets.