Acceptance by Final State and by Empty Stack
Two ways for a PDA to say yes, one guess about the middle of a palindrome, and the price of being deterministic.
What this unit covers
Unit 5: Pushdown Automata and Properties of Context-Free Languages
- 1 Pushdown Automata (PDA)Give a finite automaton a stack of plates and it can suddenly count, match and remember. · 13 min
- 2 Acceptance by Final State and by Empty StackTwo ways for a PDA to say yes, one guess about the middle of a palindrome, and the price of being deterministic. · 13 min
- 3 Equivalence of Pushdown Automata and Context-Free GrammarsA grammar that generates and a machine that recognises turn out to be two descriptions of the same languages. · 13 min
- 4 The Pumping Lemma and Closure Properties of Context-Free LanguagesEvery long enough string in a context-free language has two pieces that can be pumped together, and that is how we prove some languages are beyond any grammar. · 14 min