| 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: 5 | Munkarend: 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 | |