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.

Javítási lehetőség:

  • 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.