Nyelvek és automaták

A tantárgy angol neve: Languages and Automata 

Adatlap utolsó módosítása: 2023. január 12.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Mérnökinformatikus MSc

Közös tantárgy
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZMA12   3/0/0/f 5  
3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin,
A tantárgy tanszéki weboldala http://cs.bme.hu/nyau
4. A tantárgy előadója

Dr. Csima Judit,      egyetemi docens, SZIT 

Dr. Friedl Katalin,   egyetemi docens, SZIT 

Kabódi László,        egyetemi tanársegéd, SZIT 

Dr. Katona Gyula,   egyetemi docens, SZIT
5. A tantárgy az alábbi témakörök ismeretére épít

Alapvető gráfelméleti ismeretek, a P és NP bonyolultsági osztályok.

6. Előtanulmányi rend
Kötelező:
NEM
(TárgyEredmény( "BMEVISZMA04", "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZMA04", "FELVETEL", AktualisFelev()) > 0)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

7. A tantárgy célkitűzése

A tantárgy a legfontosabb automatatípusokkal, és a formális nyelvtanok alapjaival foglalkozik. Bemutatja az automaták és nyelvtanok közötti kapcsolatokat,   alkalmazhatóságuk határait. A hallgatók megismerkednek a fordítóprogamok készítéséhez szükséges legfontosabb elméleti alapokkal. A Turing-gépek kapcsán megismerkednek algorimussal eldönthetetlen és hatékonyan nem eldönthető problémákkal is. 

(1)  A tárgyalt  automaták és nyelvtanok megismerése, példákon szemléltetése. 

(2)  A különböző automaták és nyelvtanok közötti kapcsolatok átlátása. 

(3)   A tanult technikák alkalmazása. 

(4)  Adott problémához a megfelelő eszköz kiválasztása, alkalmazásának képessége.

8. A tantárgy részletes tematikája
  1. Ábécé, szó, nyelv fogalma. Determinisztikus véges automata. Reguláris nyelvek osztálya, és ennek zártsága unióra, metszetre, különbségre, komplementerre.
  2. Hiányos, nemdeterminisztikus és epszilon-átmenetes véges automata, ezek ekvivalenciája. A reguláris nyelvek osztálya zárt az összefűzésre és tranzitív lezárásra.
  3. Ekvivalenciareláció szavakon és egy véges automata állapotain, ezek kapcsolata. Minimálautomata.
  4. Reguláris kifejezések, ekvivalenciájuk a véges automatákkal. Nem regularitás bizonyítása, a pumpálási lemma.
  5. Formális nyelvtanok, a Chomsky hierarchia. Reguláris nyelvtanok. Reguláris nyelvekkel kapcsolatos eldöntési kérdések (üres, véges, tartalmazza-e az adott szót, egyenlő-e két nyelv)
  6. Környezetfüggetlen nyelvtanok és nyelvek. CF nyelvtanok egyszerűsítése: epszilon-szabályok, láncszabályok, felesleges szimbólumok kiküszöbölése.
  7. Környezetfüggetlen nyelvek zártsági tulajdonságai. Nem környezetfüggetlen nyelvek, a pumpálási lemma.
  8. Nemdeterminisztkus és determinisztikus veremautomata. CF nyelvtan és veremautomata kapcsolata. Determinisztikus CF nyelvek.
  9. A beletartozás eldöntése:  Cocke-Younger-Kasami-algoritmus és ennek hatékonysága. Általános elemzők.
  10. CF nyelvtanok és nyelvek egyértelműsége, példák, kapcsolat a determinisztikussággal. 
  11. Determinisztikus és nemdeterminisztikus Turing-gépek. Nemdeterminisztikus Turing-gépek determinizálása. 
  12. Az R és RE osztályok fogalma, példák. A Church-Turing-tézis. 
  13. Egy- és többszalagos Turing-gépek ekvivalenciája. Nevezetes nyelvek: diagonális, univerzális, megállási nyelv. 
  14. Az R és RE zártsági tulajdonságai. R, RE, coRE kapcsolata, további példák. 
  15. Rice-tétel és alkalmazásai. Post megfeleltetési problémája.
  16. Algoritmikus kérdések a CF nyelvtanokkal kapcsolatban: eldönthető és  eldönthetetlen problémák.
  17. Generatív nyelvek és Turing-gépek, környezetfüggő nyelvek és a lineárisan korlátozott Turing-gépek kapcsolata.
  18. Tár- és időkorlátos Turing-gépek. Tár-idő tétel. TIME, SPACE, NTIME NSPACE osztályok. Zártsági tulajdonságaik,  kapcsolatuk. 
  19. A P, NP, PSPACE, EXPTIME osztályok kapcsolata.  Tanú tétel az NP osztályra. Karp-redukció, Cook-Levin tétel a SAT NP-teljességéről.  További NP-teljes nyelvek. 
  20. Turing-gépek kapcsolata a RAM modellel, Kapcsolat az időkorlátok között.
  21. Ismétlés, tartalék.
9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

Előadás, de néhány részletet (bizonyítást) a kiadott jegyzetből önállóan kell elsajátítani.  

Hetente a tanulást segítő, a megértést ellenőrző gyakorló feladatsor (nem kell beadni).

10. Követelmények 2 zárthelyi, mindkettőn legalább 40%-ot kell elérni. A végső jegy a két zh átlagából adódik.
11. Pótlási lehetőségek

Mindkét zh-hoz 1-1 pótzh lesz, melyen az adott zh-t pótolni vagy javítani lehet. (A pótzh felülírja az eredeti zh eredményét.)

12. Konzultációs lehetőségek

Az előadóval való egyeztetés szerint.

13. Jegyzet, tankönyv, felhasználható irodalom
  • Csima Judit, Friedl Katalin: Nyelvek és automaták, elektronikus jegyzet, elérhető a tantárgy honlapjáról. 
  • Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTex, 1999. 
  • Michael Sipser: Introduction to the theory of computation, Thomson Course Techn., 2006.
14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra42
Félévközi készülés órákra28
Felkészülés zárthelyire50
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása30
Vizsgafelkészülés 
Összesen150
15. A tantárgy tematikáját kidolgozta

Dr Friedl Katalin, egyetemi docens, SZIT