- Programming club interest meeting
- Thursday (Feb. 25), 5:00 PM
- Bailey 101
- Nondeterminism and stacks?
- Think of nondeterminism as machine cloning itself, including its stack
- Think of nondeterminism as machine cloning itself, including its stack
- Lemma 2.21
- If language is context free then PDA describes it
- Context free implies CFG
- Convert that CFG into PDA
- Step 1: push $ and S on stack
- Step 2 based on top of stack
- Variable v: push right side of some rule for v
- Terminal a: read input and compare to a, continue if match, reject otherwise
- $: accept
- Example: PDA for
- E → E + T
- E → T
- T → T * a
- T → a
- Pushdown automata are equivalent to context free grammars, part 2
- Read rest of “Equivalence with Context-Free Grammars” (proof of Lemma 2.27
and related claims)
- Page 121 through 124