| Tantárgy neve: Automaták és formális nyelvek |
Tantárgy Neptun kódja: Nappali: GEMAN272-B 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:GEMAN112-B |
| Óraszám/hét: Előadás (nappali): 3 Gyakorlat (nappali): 1 | Számonkérés módja: kollokvium |
| Kreditpont: 5 | Munkarend: Nappali |
| 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 az informatikai szakterület tudásanyagát megalapozó általános és specifikus matematikai, számítástudományi elveket, tényeket, szabályokat, összefüggéseket, és eljárásokat. Az érintett területek: analízis (kalkulus), numerikus analízis, diszkrét matematika, lineáris algebra, operációkutatás, valószínűségszámítás és statisztika, logikai alapok, számításelmélet, algoritmusok tervezése és elemzése, automaták és formális nyelvek, mesterséges intelligencia alapjai. Képesség: Képes az általános és specifikus matematikai, számítástudományi elveket, tényeket, szabályokat, összefüggéseket alkalmazni informatikai szakterületen. Képes az informatika formális modelljeinek alkalmazására. Képes az informatikai szakterület tudásanyagát alkalmazni algoritmusok tervezésére, elemzésére és implementálására a legfontosabb programozási paradigmák figyelembe vételével. Attitűd: Vállalja és hitelesen képviseli informatikai szakterülete szakmai alapelveit. Nyitott a képesítésével, szakterületével kapcsolatos szakmai, technológiai fejlődés és innováció megismerésére és befogadására. Fontosnak tartja az informatikai szakmai eredmények közvetítését szakmai és nem szakmai körök számára. Autonomia és felelősség: Törekszik a hatékony és minőségi munkavégzésre. | |
| Tárgy tematikus leírása: SVé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 . | |