Begin with the grammar: S \to ASB / \epsilon A \to aAS / a B \to SbS /

Back to the 2022 paper

Module 2: Context-free languages and pushdown automata

202214m

Begin with the grammar:
$S \to ASB / \epsilon$
$A \to aAS / a$
$B \to SbS / A / bb$

(i) Eliminate $\epsilon$ -productions.
(ii) Eliminate unit productions in the resulting grammar.
(iii) Eliminate any useless symbol in the resulting grammar.
(iv) Put the resulting grammar into CNF.

Search Google Ask AI

Similar questions

FORMAL LANGUAGE & AUTOMATA THEORYEliminate \varepsilon, unit, and useless productions from the grammar: A → bA | Bba | aa B → aba | b | D C → CA | AC | B D → a | \varepsilon20237m FORMAL LANGUAGE & AUTOMATA THEORYDefine Chomsky Normal Form. Convert the CFG: S → aSb | ab | Aa A → aab to CNF.20237m FORMAL LANGUAGE & AUTOMATA THEORYCheck whether the grammar: S \to aSa \mid bSb \mid a \mid b is ambiguous.20217m FORMAL LANGUAGE & AUTOMATA THEORYShow that the following grammar is ambiguous: S \rightarrow SS | aSb | bSa | \epsilon20257m

PreviousDefine recursively enumerable languages. Let L_1 be recursive and L_2 recursively enumerable. Show that L_2 - L_1 is necessarily recursively enumerable.NextDesign a pushdown automata to accept the following language by empty stack: \{ 0^n 1^n / n \ge 1 \}.