K-INFO
HU
EN
Belépés
Tantárgy » BMEVISZM104
Régebbi verziók TAD letöltése (PDF)

Nyelvek és automaták

Languages and Automata
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
Tantárgy neve (magyarul, angolul)
Nyelvek és automaták
Languages and Automata
Tantárgykód BMEVISZM104
Tantárgyjelleg —
Képzési szint —
Kurzustípusok és óraszámok (heti/féléves)
Kurzustípus elmélet gyakorlat laboratóriumi gyakorlat
óraszám (heti) 3 0 0
jelleg (kapcsolt/önálló) — — —
Tanulmányi teljesítmény/értékelés típusa félévközi érdemjegy
Tantárgy kreditértéke 4
Tantárgyfelelős
DR. Friedl Katalin
beosztás: egyetemi docens
Tantárgyat gondozó oktatási szervezeti egység
Számítástudományi és Információelméleti Tanszék
Kar Villamosmérnöki és Informatikai Kar
Tantárgy weboldala —
Tantárgy elsődleges mintatantervi jellege —
Közvetlen előkövetelmények – Erős előkövetelmény nincs
Közvetlen előkövetelmények – Gyenge előkövetelmény nincs
Közvetlen előkövetelmények – Párhuzamos előkövetelmény nincs
Közvetlen előkövetelmények – Mérföldkő előkövetelmény nincs
Közvetlen előkövetelmények – Kizáró feltétel nincs

Célkitűzés

Tantárgyprogram
  • 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.
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.

Tanulmányi eredmények

Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:

Tudás

Nincsenek rögzített tanulási eredmények.

Képességek

Nincsenek rögzített tanulási eredmények.

Attitűd

Nincsenek rögzített tanulási eredmények.

Autonómia és felelősség

Nincsenek rögzített tanulási eredmények.

Oktatási módszertan

előadás

Tanulástámogató anyagok

Online források
Bach Iván: Formális nyelvek, TypoTex, 2001. Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTex, 1999.; Michael Sipser: Introduction to the theory of computation, Thomson Course Techn., 2006.

A tantárgy teljesítéséhez ajánlott előzetes ismeretek

Tudás típusú kompetenciák
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
Alapvető gráfelméleti ismeretek.
Képesség típusú kompetenciák
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
Alapvető gráfelméleti ismeretek.
Általános szabályok
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. 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ó.
Teljesítményértékelési módszerek
Szorgalmi időszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Szorgalmi időszakban végzett teljesítményértékelések részaránya

Nincs megadva részarány.

Vizsgaidőszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Vizsgarészek részaránya

Nincs megadva részarány.

Érdemjegy megállapítása

Nincs megadva érdemjegy határ.

Jelenléti és részvételi követelmények

Nincs megadva jelenléti követelmény.

Javítás, ismétlés és pótlás különös szabályai

Nincs megadva.

Rövid leírás

Nincs megadva.

Részletes leírás

Nincs megadva.

Ajánlott tantárgyak

Nincs megadva.

A tantárgy elvégzéséhez szükséges tanulmányi munka

Nincs megadva munkaidő bontás.

Tantárgykövetelmények hatályossága
Tantárgykövetelmények hatályosságának kezdete:
—
Tantárgykövetelmények hatályosságának vége:
—
Tantervi elhelyezés

Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.