Nyelvek és automaták

A tantárgy angol neve: Languages and Automata

Adatlap utolsó módosítása: 2008. szeptember 1.

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

Mérnök informatikus szak

MSc képzés

Közös tantárgy
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZM104 1 3/0/0/f 4  
3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin,
4. A tantárgy előadója Dr. Csima Judit
5. A tantárgy az alábbi témakörök ismeretére épít Alapvető gráfelméleti ismeretek.
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

Egyszerű automaták az informatikában sok helyen előfordulnak. A tantárgy bemutatja az alapvető automatatípusokat  és megvizsgálja, melyik típus mire alkalmas. Az automaták vizsgálata szorosan összefonódik a formális nyelvek vizsgálatával is. Cél a klasszikus automaták és a formális nyelvek közötti kapcsolatok leírása. A hallgatók megismerik a fordítóprogramok készítése során használható elméleti alapokat is. A Turing-gépek kapcsán megvizsgáljuk egyes elméleti és gyakorlati problémák és nyelvek algoritmikus bonyolultságát, különös tekintettel a P és NP nyelvosztályokra.


8. A tantárgy részletes tematikája
  • Véges automaták és reguláris nyelvek (3 hét)

    Determinisztikus és nemdeterminisztikus véges automaták. Véges automaták determinizálása és minimalizálása. Reguláris nyelvtanok és reguláris kifejezések, ezek ekvivalenciája a véges automatákkal. A reguláris nyelvek zártsági tulajdonságai, pumpálás mint a nem regularitás bizonyításának eszköze.

  • Veremautomaták és környezetfüggetlen nyelvek (3 hét)

    Veremautomaták definiciója. Környezetfüggetlen nyelvtanok és nyelvek, normál formák. A környezetfüggetlen nyelvtanok és a veremautomaták kapcsolata. A környezetfüggetlen nyelvek zártsági tulajdonságai, a pumpálás környezetfüggetlen változata. Determinisztikus és nem determinisztikus környezetfüggetlen nyelvek.

  • Turing-gépek, eldönthetőségi kérdések (3 hét)
    Turing-gép definiciója. Eldönthetőség és felismerhetőség (rekurzív, ill. rekurzívan felsorolható nyelvek). Adott nyelvbe tartozás eldöntésének nehézsége. Eldönthetőség reguláris nyelvek és környezetfüggetlen nyelvek esetén, egyszerű elemzési technikák. Egyes fontos nyelvek eldönthetősége.Turing-gépek és a 0. Chomsky nyelvosztály, illetve a lineárisan korlátolt Turing-gépek és a környezetfüggő nyelvek kapcsolata.
  • Az eldönthető nyelvek további osztályozása (2 hét)
Idő- és tárkorlátos Turing-gépek, a kétféle korlát közötti összefüggések. TIME, SPACE nyelvosztályok és hierarchiájuk. A P, PSPACE, EXPTIME nyelvosztályok.
  • Nemdeterminisztikus Turing-gépek és az NP-teljesség (2 hét)

    Az NP osztály definiciója. Az NP-teljesség fogalma, jelentősége. Alapvető NP-teljes problémák vizsgálata.

  • Kolmogorov-bonyolultság
A szavak információtartalmának mérése Kolmogorov-bonyolultsággal. Algoritmikus tömörítés és a Kolmogorov-bonyolultság. Kapcsolat a véletlenszerűséggel. Az optimális tömörítés mértékének eldönthetetlensége.
9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) előadás
10. Követelmények A félév során 4 zárthelyit iratunk. A félév teljesítésének feltétele: minden zárthelyin legalább 40 %-os teljesítmény. A végső jegy (teljesítés esetén) a négy zárthelyi átlagából adódik.
11. Pótlási lehetőségek

A szorgalmi időszak során minden zárthelyi dolgozathoz lesz pótlási (javítási) lehetőség.

A pótlási héten egyetlen alkalom lesz amikor egy tetszőleges zh dolgozat pótolható.

12. Konzultációs lehetőségek Az előadóval való egyeztetés szerint.
13. Jegyzet, tankönyv, felhasználható irodalom
  1. Bach Iván: Formális nyelvek, TypoTex, 2001.
  2. Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTex, 1999.
  3. 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ákra 30
Felkészülés zárthelyire 48
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés 
Összesen 120
15. A tantárgy tematikáját kidolgozta dr. Friedl Katalin egyetemi docens, dr. Csima Judit egyetemi adjunktus