Előadás: Hétfő 12:15-13:45, Déli ép. 2.502
Gyakorlat: Hétfő 14:15-15:45, 16:00-17:30, Déli ép. 0.311
Előadó:
Lukovszki Tamás
- | fóliák |
1. Bevezetés | |
2. Alapok, grammatikák, nyelvek | |
3. Grammatikák, Kontrollált grammatikák, L-rendszerek | |
4. Reguláris kifejezések, reguláris nyelvek, véges automaták | |
5. Véges automaták (VA), DVA, NVA, minimális DVA, reguláris pumping lemma | |
6. Probabilisztikus automaták, veremautomaták, környezetfüggetlen grammatikák, környzetfüggetlen pumping lemma | |
7. Turing gép, változatok, Church-Turing tézis, rekurzívan felsorolható nyelvek, 0. típusú grammatikák |
M. Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage, 2012.
J. E. Savage, Models of Computation: Exploring the Power of Computing,
Brown University, 1998.
https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation.pdf