Let G be a CFG in CNF with b variables. Show that if G derives any str

Back to the 2021 paper

Module 2: Context-Free Languages (CFL) and PDA

20217m

Let $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.

Search Google Ask AI

Similar questions

Formal Language & Automata TheoryLet 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.20217m Formal Language & Automata TheoryUsing the following grammar S \to AB \mid BC A \to BA \mid a B \to CC \mid b C \to AB \mid a use the CYK algorithm to determine whether the given string baaba is in L(G) or not.20197m 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 TheoryConsider the grammar: S \to AB \mid BC A \to BA \mid a B \to CC \mid b C \to AB \mid a Use the CYK algorithm to determine whether the given string "baaba" is in L(G) or not.202114m

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

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