Prove that if L is generated by a CFG, then L is accepted by a non-det

Back to the 2020 paper

Module 2: Context-free languages and pushdown automata

20207m

Prove that if $L$ is generated by a CFG, then $L$ is accepted by a non-deterministic PDA by empty stack.

Similar questions

FORMAL LANGUAGE & AUTOMATA THEORYProve that if L is accepted by a PDA, then L can be generated by a CFG.20227m Formal Language & Automata TheoryConstruct a PDA that accepts the language L = \{a^{2n}bc \mid n \ge 0\} by final state and empty stack.20217m FORMAL LANGUAGE & AUTOMATA THEORYDesign a PDA (empty stack and final state both) for L = \{ WW^r \mid W \in \{a,b\}^* \}.20237m 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

PreviousShow given grammar over alphabet \{a, b\} verify whether it is ambiguous or unambiguous: S \to a \mid abSb \mid aAb A \to bS \mid aAAb NextDesign a pushdown automaton for the following context-free grammar: S \to aB \mid bA A \to aS \mid bAA \mid a B \to bS \mid aBB \mid b

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