Elmélet: 50 %

Gyakorlat: 50 %

A tantárgy tantervi helye: 2. félév

Munkarend: Nappali

Előtanulmányi feltételek:

Értékelés: kollokvium

Tantárgy besorolása: kötelezően választható

Oktatás nyelve: Magyar

Tantárgyfelelős: Dr. Alvarez Gil Rafael Pedro

Felelős tanszék: Informatika Tanszék

Tantárgy oktatója(i): Dr. Bolla Kálmán Milán , Dr. Bolla Kálmán Milán

Ellenőrzésért felel: Prof. Dr. Johanyák Zsolt Csaba

Tárgy oktatásának célja:
Az automatákra, a formális nyelvekre, és a kapcsolatukra vonatkozó alapismeretek elsajátítása.

Elsajátítandó ismeretanyag előadás:

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.

Elsajátítandó ismeretanyag laboratórium:

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.

Elsajátítandó szakmai kompetenciák (tudás, képesség, attitűd, autonómia és felelősség, további szakmai kompetenciák):
Tudása:

- 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égei:

- 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űdje:

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

További szakmai kompetenciák:

A számonkérés és értékelés rendszere:
Félévközi tanulmányi követelmények:
A félév során a hallgatók egy 30 pontos elméleti zárthelyi dolgozatot írnak előadáson, két 25 pontos zárthelyi dolgozatot a laboratóriumban, és az órákon kívül elkészítenek egy 20 pontos nagy feladatot. Az elméleti zárthelyi dolgozat akkor sikeres, ha a hallgató legalább 15 pontot elér. A gyakorlat akkor sikeres, ha a két gyakorlati zárthelyi dolgozaton együttesen legalább 25 pontot, az órákon kívül elkészített nagy feladatban legalább 10 pontot elér a hallgató. Sikeres elméleti zárthelyi dolgozat és gyakorlat esetén a hallgató vizsgára bocsátható. Az oktató a félév első hetében tájékoztatja a hallgatókat a zárthelyi dolgozatok 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.

Tanulmányi segédanyagok, laborháttér:

Neptun Meet Street-re feltöltött gyakorlati segédanyagok. A laboratóriumokban minden hallgatónak külön, korszerű számítógépes hozzáférés biztosított.

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