K-INFO
HU
EN
Belépés
Tantárgy » BMEVISZMA12
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 BMEVISZMA12
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 5
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 http://cs.bme.hu/nyau
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
  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.
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.

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, 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).

Tanulástámogató anyagok

Online források
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.

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, a P és NP bonyolultsági osztályok.
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, a P és NP bonyolultsági osztályok.
Általános szabályok
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. 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.)
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.