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 THEORYGiven the grammar G = (\{S\}, \{a, b\}, P, S) P: S \rightarrow aSb | ab Derive the string aabb using leftmost derivation, rightmost derivation and also draw the parse tree.20257m Formal Language & Automata TheoryUsing Pumping Lemma for CFLs, prove that L = \{a^{n}b^{n}c^{n} \mid n \ge 0\} is not context-free.20257m Formal Language & Automata TheoryAssume that a regular language L is provided to you as a DFA M(\{Q, \Sigma, \delta, q_0, F\}). How would you check whether L is infinite?20197m

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.

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.

Get on Google Play