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 (states, input alphabet, stack alphabet, transition function, start state, accept states)
Theorem
A language is context free if and only if some pushdown automaton recognizes it.
2.3
The pumping lemma for context-free languages
1. for each i ³ 0 , uvixyiz ÎA
2. |vy| > 0
3. |vxy| £ p