Automaták és formális nyelvek (MSC_INF_5_L)
Alapadatok
Oktatók
Tantárgy célja
Az automatákra, a formális nyelvekre, és a kapcsolatukra vonatkozó alapismeretek elsajátítása.
Elsajátítandó ismeretanyag
Alapfogalmak. Nyelvek. Generatív grammatikák. A Chomsky-féle hierarchia. Véges automaták. Nemdeterminisztikus véges automaták. Determinisztikus és nemdeterminisztikus véges automaták. Reguláris nyelvek. A jobblineáris nyelvek, a reguláris nyelvek és a véges automaták ekvivalenciája. Mealy és Moore automaták. Környezetfüggetlen nyelvtanok és nyelvek. A Chomsky-féle normálforma. Derivációs fák, bal- ill. jobboldali levezetések. Determinisztikus és nemdeterminisztikus veremautomaták. A veremautomaták és a környezetfüggetlen nyelvtanok ekvivalenciája. Általános nyelvtanok és környezetfüggő nyelvtanok. A Turing-gép. Rekurzíven felsorolható és rekurzív nyelvek. Eldönthetőség és kiszámíthatóság.
Szakmai kompetenciák
Tudás
- Ismeri a műszaki informatikai rendszerek fejlesztéshez szükséges, széles körben alkalmazható problémamegoldó technikákat. - Érti az informatikai alkalmazások fejlesztéshez szükséges természettudományos és mérnöki módszerek elvét. - Az informatikai szakmán belül, a specializációtól függően mélyebb elméleti és gyakorlati ismeretekkel rendelkezik az alábbiak közül egy vagy néhány területen: szoftvertervezés, rendszerszimuláció és -modellezés, kommunikációs hálózatok, mobil- és erőforrás-korlátos alkalmazások, számítógépes grafika és képfeldolgozás, kritikus és beágyazott rendszerek, médiainformatika, IT-biztonság, párhuzamos rendszerek, intelligens rendszerek, számításelmélet, adatbázisok.
Képesség
- Képes törvényszerűségeket, összefüggéseket feltárni és megérteni. - A megszerzett tudást képes alkalmazni és a gyakorlatban hasznosítani. - Képes problémamegoldó technikákat használni a szoftver- és alkalmazásfejlesztés során. - Képes az informatikához kapcsolódó tudományokban a megszerzett szakmai tapasztalat ismereti határairól származó információk, felmerülő új problémák, új jelenségek feldolgozására. - Az információtechnológia eszközeit és formális módszereit készség szinten használja. - Megérti az alkalmazás követelményeit. - Javaslatait az alkalmazói környezet szakértőinek el tudja magyarázni.
Attitűd
- Nyitott és elkötelezett az önművelésre, önfejlesztésre, az egyéni tudás, ismeret elmélyítésére, bővítésére a természettudományok, a mérnöki és informatikai tudományok területén.
Autonómia és felelősség
- Felelősséget érez a határidők betartására és betartatására. - Önállóan tölt be informatikai munkakört, amelyben a teljes folyamatot kezében tartva, szakmailag felelős módon dolgozik. - Alkalmas csoportban, egy-egy részterület szakértőjeként dolgozni, valamint csoportot felelősséggel irányítani.
Számonkérés és értékelés
Félévközi követelmények
A félév során a hallgatók egy 60 pontos zárthelyi dolgozatot írnak, amely elméleti kérdésekből és megoldandó gyakorlati feladatokból áll, és a konzultációkon kívül elkészítenek egy 40 pontos nagy feladatot. A zárthelyi dolgozat akkor sikeres, ha a hallgató legalább 30 pontot elér. A konzultációkon kívül elkészített nagy feladat akkor sikeres, ha a hallgató legalább 20 pontot elér. Sikeres zárthelyi dolgozat és konzultációkon kívül elkészített nagy feladat esetén a hallgató vizsgára bocsátható. Az oktató a félév első konzultációján tájékoztatja a hallgatókat a zárthelyi dolgozat helyéről és idejéről, és a nagy feladattal kapcsolatos tudni valókról.
Vizsgakövetelmények
A vizsgán a hallgató írásbeli dolgozatot ír gyakorlati feladatokból. Amennyiben az írásbeli dolgozatban eléri az összpontszám 50%-át , a kiadott szóbeli tételsorból húzott tétel alapján szóbeli vizsgát tesz.
Generatív MI használata
Nincs megadva
Irodalom
Kötelező irodalom
Ésik Zoltán, Gombás Éva, Iván Szabolcs: Automaták és formális nyelvek példatár, Egyetemi tananyag, Typotex Kiadó, 2011, ISBN 978-963-279-495-2. Letölthető: https://dtk.tankonyvtar.hu/xmlui/handle/123456789/7570 Bach Iván: Formális nyelvek - Második, javított kiadás, Egyetemi tankönyv, Typotex kiadó, 2002, ISBN 9639132-92-6. Letölthető: https://www.typotex.hu/download/formalisnyelvek.pdf
Ajánlott irodalom
V. Ravi Sankar: Understanding Automata, Formal Languages and Grammar, Alpha Science International, Limited, 2021, ISBN 1783325453, 9781783325450 J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation: Pearson New International Edition, Pearson Education Limited, 2013, ISBN: 1292039051 Peter Linz: An Introduction to Formal Languages and Automata, 5th edition, Jones & Bartlett Publishers, Sudbury, MA, USA, 2012, ISBN 978-1-4496-1552-9