Automaták és formális nyelvek (MSC_INF_5_L)

Alapadatok
Szak és képzési szint
Mérnökinformatikus, MSc
Tanterv
2023
Óraszám
16 (Konzultáció)
Kreditérték
5 kredit
Elmélet–Gyakorlat arány
Elmélet: 0%, Gyakorlat: 0%
Tantervi félév
2. félév
Munkarend
Levelező
Előfeltételek
–
Értékelés típusa
kollokvium
Tárgy kategória
kötelezően választható
Nyelv
magyar
Oktatók
Tantárgyfelelős
Dr. Alvarez Gil Rafael Pedro
Felelős tanszék
Informatika Tanszék
Oktatók
Dr. Bolla Kálmán Milán, - nincs
Ellenőrzésért felel
Prof. Dr. Johanyák Zsolt Csaba
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

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.

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