Skriptá
Nasledujúce skriptá pokrývajú veľkú časť oboch semestrov tohto predmetu:
- B. Rovan, M. Forišek: Formálne jazyky a automaty
Poznámky k cvičeniam
- Cvičenie č. 1. Formálne jazyky a operácie na nich.
- Cvičenie č. 2. Homomorfizmy a inverzné homomorfizmy.
- Cvičenie č. 3. Bezkontextové gramatiky (1. časť).
- Cvičenie č. 4. Bezkontextové gramatiky (2. časť).
- Cvičenie č. 5. Konečné automaty.
- Cvičenie č. 6. Regulárne jazyky.
- Cvičenie č. 7. Zásobníkové automaty.
- Cvičenie č. 9. Bezkontextové jazyky.
- Cvičenie č. 10. Turingove stroje.
- Kódovanie Turingových strojov a univerzálny Turingov stroj.
- Cvičenie č. 11. Rozhodnuteľnosť.
- Cvičenie č. 12. Základy výpočtovej zložitosti.
Odporúčaná literatúra
| [1] | Hopcroft, J. E.; Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, prvé vydanie, 1979. [ CVTI ]
Klasická učebnica formálnych jazykov a automatov, ktorá sa asi najviac blíži obsahu tejto prednášky. |
| [2] | Hopcroft, J. E.; Ullman, J. D.: Formálne jazyky a automaty. Alfa, 1978. [ Akademická knižnica UK ] [ CVTI ]
Slovenský preklad knihy, ktorá bola „predchodcom” učebnice [1]. |
| [3] | Kozen, D. C.: Automata and Computability. Springer, 1997.
Výborná kniha pre „náročnejších čitateľov”, v ktorej možno nájsť aj o niečo pokročilejšiu látku a plno zaujímavých cvičení. |
| [4] | Howie, J. M.: Automata and Languages. Clarendon Press, 1991.
Úvod do formálnych jazykov a automatov z pohľadu algebraika. |
| [5] | Hopcroft, J. E.; Motwani, R.; Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, tretie vydanie, 2007. [ Akademická knižnica UK ]
Najnovšie (ale nie najlepšie) vydanie knihy [1]. |