1. How to prove a language is CFL?
Write its context free grammar.
Design a push down automata for the language.
Apply closure properties.
2. How to prove a language is non-CFL?
•Use pumping theorem to prove it is not context free.
•Apply closure properties.
3. Classes of Languages
- Recursive = decidable: their Turing machine always halt
- Recursively Enumerable (RE) but not recursive: their Turing machine halt if they accept
- Non recursively enumerable (non-RE): there are not Turing machine for them.