5 kreditértékű, Kötelező tárgycsoportba tartozó tantárgy, 3. félévben ajánlott.
Eddig
| Tantárgy neve | Félév | Tárgycsoport |
|---|---|---|
| Diszkrét matematika - 1 | 1 | Kötelező |
| Tantárgy neve | Félév | Tárgycsoport |
|---|---|---|
| Algoritmusok tervezése és elemzése | 6 | Kötelező |
| Automataelméleti alkalmazások programozása | Szabadon választható | |
| Fordítóprogramok | (A) Mesterséges intelligencia sáv | |
| Automataelméleti alkalmazások | Szabadon választható | |
| DNS számítógépek és formális modelljeik | Szabadon választható |
Chomsky hierarchia, üresszó lemma + bizonyítás
Formális rendszer és néhány főbb típusa
Automaták fogalma és főbb típusai
Automata leképezés fogalma, Raney tétel + bizonyítás
Automaták ekvivalenciája, Gill tétel + bizonyítás
Redukált automaták, Aufenkamp-Hohn féle eljárás + bizonyítás
Véges automaták analízise, McNaughton módszer + bizonyítás
Véges automaták szintézise, Gluskov módszer
Automaták és nyelvek kapcsolata
Nyelvtanok normális alakra hozása, Chomsky-féle normálalak
Bar-Hillel lemma + bizonyítás
Hossz nemcsökkentű nyelvtanok és kapcsolatuk az 1-es típusú nyelvtanokkal
Kuroda-féle normálalak + bizonyítás
Révész-féle normálalak + bizonyítás
Rekurzív-, és rekurzívan felsorolható nyelvek, eldönthetőség
Univerzális Turing-gép, Turing-gépek megállási problémája + bizonyítás