Nyomtatás

Miskolci Egyetem - Gépészmérnöki és Informatikai Kar

TANTÁRGYI TEMATIKA

Automaták és formális nyelvek; MSc (Nappali+Levelező)

Tantárgy neve:
Automaták és formális nyelvek
Tantárgy Neptun kódja:
Nappali: GEMAN385M
Levelező: GEMAN385ML
Tárgyfelelős intézet:
MAT - Matematikai Intézet
Tantárgyelem: A
Tárgyfelelős: Dr. Radeleczki Sándor - egyetemi tanár
Közreműködő oktató(k): dr. Veres Laura.
Javasolt félév: 4 Előfeltétel:
Óraszám/hét:
Előadás (nappali): 3
Gyakorlat (nappali): 1
Számonkérés módja: kollokvium
Kreditpont: 5Munkarend: Nappali+Levelező
Tantárgy feladata és célja:
Nyelvekre és automatákra vonatkozó alapvető ismeretek elsajátítása, egyéb számítástudományi tárgyak megalapozása
Tudás: Ismeri a villamosmérnöki szakmához kötött természettudományos és műszaki elméletet és gyakorlatot, rendelkezik a megfelelő szintű manuális készségekkel. Átfogó ismeretekkel rendelkezik a számítógép-hardverekről és -szoftverekről, továbbá a számítógépek és számítógép-hálózatok alkalmazástechnikájáról.
Képesség: Képes a villamosrendszerek és -folyamatok üzemeltetése során gyűjtött információ feldolgozására és rendszerezésére, elemzésére, következtetések levonására. Képes rendszerszemléletű, folyamatorientált gondolkodásmód alapján komplex rendszerek globális tervezésére.
Attitűd: Törekszik szakmailag magas szinten önállóan vagy munkacsoportban megtervezni és végrehajtani a feladatait. Törekszik arra, hogy a munkáját rendszerszemléletű és folyamatorientált gondolkodásmód alapján komplex megközelítésben végezze. Nyitottan áll az önművelést, önfejlesztést szolgáló szakmai továbbképzésekhez.
Autonomia és felelősség: Szakmai problémák megoldása során önállóan és kezdeményezően lép fel.
Tárgy tematikus leírása:
Véges determinisztikus és nondeterminisztikus automaták, elfogadott nyelv. Mealy és Moore automaták. Reguláris nyelvek és véges automaták kapcsolata, Kleene tétele. Reguláris nyelvek zártsági tulajdonságai. Myhill-Nerode tétele, véges det. automaták minimalizálása. Véges automaták, mint felismerők. Környezetfüggetlen nyelvtanok és nyelvek. Derivációs fák. Nondeterminisztikus és determinisztikus veremautomaták. Veremautomaták és környezetfüggetlen nyelvtanok ekvivalenciája. Környezetfüggetlen nyelvtanok ekvivalens átalakításai. Bar-Hillel lemma. Zártsági tulajdonságok. Turing gépek, korlátos Turing gépek. Rekurzíven felsorolható és rekurzív halmazok. Eldönthetőség és kiszámíthatóság, Turing eredménye. Generatív nyelvtanok, Chomsky hierarchia tétele. Szintaktikus elemzés. Tár és idő: Polinomiális idejű algoritmusok
Félévközi számonkérés módja és az aláírás megszerzésének feltétele (Nappali):
Az aláírás feltétele két 45 perces évközi zárthelyi dolgozat, vagy azok pótlásának eredményes (legalább 50%) megírása.
Félévközi számonkérés módja és az aláírás megszerzésének feltétele (Levelező):
Gyakorlati jegy / kollokvium teljesítésének módja, értékelése (Nappali):
A vizsga 1óra 30 perzces irásbeli dolgozat, ami elméleti és gyakorlati feladatokból áll. Az írásbeli dolgozatok értékelése:
0-49%: elégtelen (1)
50-61%: elégséges (2)
62-73%: közepes (3)
74-85%: jó (4)
86-100%: jeles (5)
Gyakorlati jegy / kollokvium teljesítésének módja, értékelése (Levelező):
Kötelező irodalom:
1.Fülöp Zoltán, Formális nyelvek és szintaktikus elemzésük, Polygon Kiadó, Szeged, 1999 2. Bach Iván, : Formális nyelvek egyetemi jegyzet, BME, Typotex Kiadó, 2001.
3.. J. K. Truss, Discrete Mathematics, Addison :Weesley, 1991
4.
5.
Ajánlott irodalom:
1.. J. Demetrovics, J. Denev és R. Pavlov, A számítástudomány matematikai alapjai, Nemzeti Tankönyvkiadó, Budapest, 1999.
2. John E. Hopcroft and Jefrey D. Ullman, Introduction to automata theory, languages and computatition, Addison- Wisley, 1979