2.1
Concepts: Substitution Rule (Production), Variable, Terminal, DeriVation
Definition: a Context-Free Grammar IS A 4-Tuple (Variables, Terminals, Rules, Start Variable)
Chomsky Normal Form:
A ®B, C
A ® a
THEOREM: ANY Context Free Language Is Generated by a Context-Free Grammar in Chomsky Normal Form.
2.2
A Pushdown Automaton IS A 6-Tuple (State, Input Alphabet, Stack Alphabet, Transition Function, Start State, Accept State)
Theorem
A Language IS Context Free IF and ONLY SOME PUSHDOWN Automaton Recognizes It.
2.3
The Pumping Lemma for Context-Free Languages 1.
For Each I
3
0, UVIXYZ
Î
A
2. | VY |> 0 3. | VXY | £ P
