1. Podać definicję języka formalnego.
2. Scharakteryzować podejście generacyjne i podejście akceptorowe do definiowania składni języka formalnego.
3. Zilustrować i scharakteryzować hierarchię języków formalnych wg N. Chomsky’ego.
4. Podać definicję gramatyki kombinatorycznej wg Chomsky’ego i języka generowanego taką gramatyką.
5. Podać definicję wyrażenia regularnego i zilustrować ją odpowiednim przykładem.
6. Podać definicję deterministycznego automatu skończonego i zilustrować ją odpowiednim przykładem.
7. Podać definicję niedeterministycznego automatu skończonego i zilustrować ją odpowiednim przykładem.
8. Przytoczyć lemat o pompowaniu dla języków regularnych.
9. Podać definicję gramatyki bezkontekstowej i zilustrować ją odpowiednim przykładem.
10. Podać definicję drzewa wywodu napisu w gramatyce bezkontekstowej i zilustrować ją odpowiednim przykładem.
11. Do czego służy notacja BNF? Podać przykład zastosowania.
12. Przytoczyć lemat o pompowaniu dla języków bezkontekstowych.
13. Podać definicję deterministycznego automatu ze stosem.
14. Podać definicję niedeterministycznego automatu ze stosem.
15. Podać definicję jednotaśmowej deterministycznej maszyny Turinga i zilustrować ją odpowiednim przykładem.
16. Do jakiej klasy można zaliczyć języki obliczane przez maszyny Turinga?