Design a pushdown automaton for the following context-free grammar: S — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2020 paper

Module 2: Context-free languages and pushdown automata

20207m

Design 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$

Search Google Ask AI

Similar questions

Formal Language & Automata TheoryConstruct a push-down automata that accepts the following language: L = \{uawb \mid u \text{ and } w \in \{a, b\}^* \text{ and } |u| = |w|\}20197m Formal Language & Automata TheoryConstruct a push-down automata that accepts the following language: L = \{uawb : u \text{ and } w \in \{a, b\}^* \text{ and } |u| = |w|\}20217m Formal Language & Automata TheoryConvert the following context-free grammar into GNF: S \to XY X \to YS \mid b Y \to SX \mid a20197m Formal Language & Automata TheoryDesign a pushdown automata for accepting the string for the language L = \{WW^R \mid W \in \{a, b\}^*\} by the empty stack as well as final state.20207m

PreviousProve that if L is generated by a CFG, then L is accepted by a non-deterministic PDA by empty stack.NextDesign a turing machine that accepts all palindromes over \Sigma = \{a, b\}.