CFG and PDA Flashcards
What does Lecture 12 aim to prove?
That context-free grammars and pushdown automata are equivalent in expressive power.
What does CFG ⇒ PDA mean?
For any context-free grammar, there exists a PDA that accepts the same language.
What does PDA ⇒ CFG mean?
For any PDA, there exists a CFG that generates the same language.
What does the PDA constructed from a CFG simulate?
Leftmost derivations of the grammar.
How many states does the PDA constructed from a CFG have?
Two states: one for setup, one for simulation.
What does the stack alphabet of a PDA from a CFG contain?
All terminals and non-terminals of the grammar: Σ ∪ V.
What are the three types of transitions in the CFG ⇒ PDA construction?
(1) Push start symbol S, (2) Replace non-terminal X with production w, (3) Match and pop terminal symbols.
When does the PDA accept in the CFG ⇒ PDA construction?
When input is fully read and the stack is empty.
Give a CFG that generates the language L = { ww^R | w ∈ {a
b}* }.
What transition does the PDA use to begin simulating a CFG?
(1, ε, ε) → (2, S) — pushes the start symbol S onto the stack.
What does DFA ⇒ CFG demonstrate?
That all regular languages are also context-free.
How is a CFG constructed from a DFA?
States become non-terminals; transitions become productions; accepting states allow ε-productions.
Give an example CFG for a DFA that accepts strings containing ‘baa’.
S → aS | bP, P → aQ | bP, Q → aR | bP, R → aR | bR | ε
What is the idea behind converting a PDA to a CFG?
Define grammar variables A_{pq} that describe stack-emptying paths from p to q.
Is the PDA ⇒ CFG construction examinable?
No — it’s covered conceptually but not tested.
What are context-free languages closed under?
Union, concatenation, and Kleene star.
How do you construct a CFG for the union of two CFLs?
Use a new start symbol S and add rules S → S₁ | S₂, where S₁ and S₂ are the original start symbols.
How do you construct a CFG for the concatenation of two CFLs?
Add a rule S → S₁ S₂, combining the start symbols of the two grammars.
How do you construct a CFG for the Kleene star of a CFL?
Add rules S → ε and S → S S to allow repetition.
What is a leftmost derivation?
A derivation where the leftmost non-terminal is always the one replaced at each step.
Why are leftmost derivations important?
They standardize derivations and are used in parsing and PDA simulations.
