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 THEORYGiven the following context-sensitive grammar: S \rightarrow aSBC | abc CB \rightarrow BC aB \rightarrow ab bB \rightarrow bb bC \rightarrow bc cC \rightarrow cc Identify the language generated by the grammar. Derive the string aabbcc step by step.20257m FORMAL LANGUAGE & AUTOMATA THEORYConstruct NPDA for the grammar: S \to \alpha ABB \mid \alpha AA \\ A \to \alpha BB \mid \alpha \\ B \to bBB \mid A20237m

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 \}.

Student FinanceWeb Platform

Pocketly — Personal Finance for Students

Keep your hostel and college expenses under control. Track accounts, log spending in seconds, and stay within your monthly budget.

Open Pocketly