Balogh Vanda - demonstrátor, SZTE
Formális nyelvek gyakorlat
2016/17 őszi félév
Tantárgykódok: IB403g-2, IB403g-6
Követelmények
- A gyakorlat látogatása kötelező.
- Két, egyenként 5 pontos házi feladat beadása a JFLAP alkalmazásával (fájlban és papíron benyújtva) a feladat kiadásától számítva kéthetes határidővel. A határidő után benyújtott feladatok nem kerülnek értékelésre.
- Egy 30 pontos zárthelyi dolgozat megírása a szorgalmi időszakban, melynek időpontja és helye a szorgalmi időszak első két hetében kerül rögzítésre.
A gyakorlaton összesen 40 pont szerezhető, melyből a zárthelyi dolgozaton minimum 10, összesen pedig minimum 16 pont szükséges a teljesítéshez.
- Amennyiben a hallgató zárthelyi dolgozatának pontszáma vagy összpontszáma nem éri el az elvárt minimális értéket, egy 30 pontos javító dolgozat írható, melynek témaköre megegyezik a zárthelyi dolgozatéval. A javítás sikeres, ha a javító dolgozat pontszámával helyettesítve a zárthelyi dolgozat pontszámát a hallgató teljesíti a fenti minimum feltételeket. Ebben az esetben azonban a gyakorlat összpontszáma csak a minimális 16 pont.
- A zárthelyi dolgozat írásának időpontjában igazoltan hiányzó hallgató a javító dolgozat időpontjában pótdolgozatot írhat. Ebben az esetben a pótdolgozaton elért teljes pontszám kerül beszámításra.
A javító, illetve pótdolgozat írásának időpontja a szorgalmi időszak első két hetében kerül rögzítésre.
Sikeres teljesítés esetén a gyakorlat érdemjegye az összpontszám alapján, sávosan kerül meghatározásra az alábbiak szerint:
- 0 - 15 pont : elégtelen (1)
- 16 - 21 pont : elégséges (2)
- 22 - 27 pont : közepes (3)
- 28 - 33 pont : jó (4)
- 34 - 40 pont : jeles (5)
Tematika
Nyelvek. Műveletek nyelveken. Reguláris nyelvek. Determinisztikus és nemdeterminisztikus automaták. Determinizálás. Jobblineáris nyelvtanok. A véges automaták, jobblineáris nyelvtanok és reguláris nyelvek ekvivalenciája. A reguláris nyelvek zártsági tulajdonságai. A reguláris nyelvek pumpáló lemmája. Eldöntési kérdések reguláris nyelvekre.
Környezetfüggetlen nyelvtanok és nyelvek. A Chomsky-féle normálforma. Derivációs fák és bal- ill. jobboldali levezetések. Egyértelmű nyelvtanok és nyelvek. Veremautomaták. A környezetfüggetlen nyelvtanok és veremautomaták ekvivalenciája. Determinisztikus környezetfüggetlen nyelvek. Műveletek környezetfüggetlen nyelveken. A környezetfüggetlen nyelvek pumpáló lemmája. Eldöntési kérdések környezetfüggetlen nyelvekre. A CYK algoritmus.
Általános nyelvtanok és környezetfüggő nyelvtanok. A Chomsky-féle hierarchia. Lineárisan korlátos automaták és Turing gépek.
Ajánlott irodalom:
- Ésik Zoltán, Gombás Éva, Iván Szabolcs: Automaták és formális nyelvek példatár, Typotex Kiadó, 2011.
Jegyzet letöltése PDF formátumban - Fülöp Zoltán: Formális nyelvek és szintaktikus elemzésük, Polygon, Szeged, 1999.
- Gécseg Ferenc: Automaták és formális nyelvek, Polygon, Szeged, 2005.
- Peter Linz: An Introduction to Formal Languages and Automata, 5th edition, Jones & Bartlett Publishers, Sudbury, MA, USA, 2012.
- Susan H. Rodger and Thomas W. Finley: JFLAP An Interactive Formal Languages and Automata Package, Jones & Bartlett Publishers, Sudbury, MA, USA, 2006.
- JFLAP program, letölthető: http://www.jflap.org/
- J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979.
- D. Kozen: Automata and Computability, Undergraduate text in computer science, Springer-Verlag, 1997.
- M. Sipser: Introduction to the Theory of Computation, PWS Publishing Company, 19975.
- W. Thomas, Automata on Infinite Objects, in: Handbook of Theoretical Computer Science, (szerk. J. van Leeuwen) B kötet, Elsevier, Amasterdam, 1990, 133-191.