Nyelvek és automaták

Nyelvek és automaták

Tárgykód	VISZMA04
Általános infók
Szak	infoMSC
Kredit	4
Ajánlott félév	Őszi
Követelmények
NagyZH	2 db
Házi feladat	opcionális
Vizsga	nincs
Elérhetőségek
Levlista	infomscATsch.bme.hu
Tantárgyi adatlap
Tárgyhonlap

Követelmények

A félév során 2 zárthelyit iratunk. A félév teljesítésének feltétele: minden zárthelyin legalább 40 %-os teljesítmény. A végső jegy (teljesítés esetén) a zárthelyik átlagából adódik.

Hasznos Infók

• Előadó: Friedl Katalin (2021)
• A tárgy ötéves megfelelője: Formális nyelvek

Segédanyagok

Jegyzetek

• Hivatalos jegyzet
• Gépelt Peabe-jegyzet (100% TL;DR) 2020 ősz
• Legépelt jegyzet 2010 ősz
• Kiegészítő anyag 2017 - CYK algoritmus

Könyv

• Formális nyelvek (Bach Iván)
• Algoritmusok (Ivanyos Gábor; Szabó Réka; Rónyai Lajos)

Gyakorlatok

Hivatalos, kötelező gyakorlat ugyan nincs a tárgyból, azonban minden évben szokott lenni fakultatív konzultáció, ahol a tárgyoldalra kirakott feladatsorokat veszik végig.

Gyakorlat 2021

• 1. Véges automaták
• 2. Minimálautomata, reguláris kifejezés
• 3. Pumpálási lemma. Nyelvtanok
• 4. CF nyelvtanok átalakítása
• 5. CF nyelvek, pumpálás
• 6. Algoritmikus kérdések, CYK algoritmus
• 7. Turing-gépek, R, RE
• 8. R, RE
• 9. PCP. Algoritmikus kérdések
• 10. Fordítók
• 11. Veremfordító, függvényt számoló Turing-gép. Idő és tár

Gyakorlat 2017

Gyakorlati anyag 2017

Szorgalmi, nehéz feladatok 2017

Gyakorlat 2014

Feladatok	Megoldás
Véges automaták	Véges automaták - megoldások
Nemdeterminisztikus véges automaták	Nemdeterminisztikus véges automaták - megoldások
Minimalizálás	Minimalizálás - megoldások
Pumpálás	Pumpálás - megoldások
Reguláris nyelvek	Reguláris nyelvek - megoldások
Nyelvtanok	Nyelvtanok - megoldások
CF nyelvtanok átalakításai, egyértelműség	CF nyelvtanok átalakításai, egyértelműség - megoldások
CF pumpálás	CF pumpálás - megoldások
Veremautomaták	Veremautomaták - megoldások
Veremautomaták és CF nyelvtanok	Veremautomaták és CF nyelvtanok - megoldások
Chomsky-normálforma, CYK algoritmus	Chomsky-normálforma, CYK algoritmus - megoldások
Turing-gép	Turing-gép - megoldások
k-szalagos Turing-gép	k-szalagos Turing-gép - megoldások
Kiszámolós TG, nevezetes nyelvek, R, RE	Kiszámolós TG, nevezetes nyelvek, R, RE - megoldások
R, RE, Nevezetes nyelvek	R, RE, Nevezetes nyelvek - megoldások
Rice tétel, PCP	Rice tétel, PCP - megoldások
Nyelvtanok és TG-ek	Nyelvtanok és TG-ek - megoldások
Tár- és időbonyolultság	Tár- és időbonyolultság - megoldások

Gyakorlat 2012

Feladatok	Megoldás
Véges automaták	Véges automaták, Nemdeterminisztikus véges automaták - megoldások
Nemdeterminisztikus véges automaták	Véges automaták, Nemdeterminisztikus véges automaták - megoldások
Minimalizálás	Minimalizálás, Pumpálás - megoldások
Pumpálás	Minimalizálás, Pumpálás - megoldások

Gyakorlat 2011

• NyA-2011Osz-Gyakorlat-Feladatok.zip
• 2011. 3 ZH előtti gyakorlatok

Gyakorlat 2010

(Nem hivatalos megoldások, tehát tartalmazhatnak hibát, csak saját felelősségre!)

• 1. gyakorlat (2010.09.09) Feladatsor
• 2. gyakorlat (2010.09.16) Feladatsor Megoldás
• 3. gyakorlat (2010.09.23) Feladatsor Megoldás
• 4. gyakorlat (2010.09.30) Feladatsor Megoldás
• 5. gyakorlat (2010.10.14) Feladatsor Megoldás
• 6. gyakorlat (2010.10.21) Feladatsor Megoldás (6/1 c. feladatnál a megoldás jó, de nem az algoritmus szerint van átalakítva. ZH-n az algoritmust kell használni)
• 7. gyakorlat (2010.10.28) Feladatsor Megoldás
• 8. gyakorlat (2010.11.04) Feladatsor Megoldás
• 9. gyakorlat (2010.11.11) Feladatsor Megoldás (Frissült 2010.12.04-én)
• 10. gyakorlat (2010.11.18) Feladatsor Megoldás
• 11. gyakorlat (2010.11.25) Feladatsor Megoldás
• 12. gyakorlat (2010.12.02) Feladatsor Megoldás

ZH-k

Két zh lesz, ezeken az anyaghoz kapcsolódó feladatokat kell megoldani, illetve az órai anyagot számonkérő elméleti kérdés(ek)re kell válaszolni. Minden zh a hozzá tartozó pótzh-n pótolható/javítható (általában egy héttel később kedd/csütörtök). Egy zh pótolható ezen felül a pótlási héten (pótpótzh). A 2014-es őszi félévtől kezdve egy elméleti kérdés (tétel, vagy definíció kimondása, esetleg egyszerűbb bizonyítás vagy órán tanult konstrukció) is van.

2. ZH tippek

Az alábbi témákat érdemes a zh-ra tudni: CYK, Chomsky normál forma, Mealy-Moore oda-vissza alakítás, pumpálási lemma CF nyelvtanokhoz.

Új tárgy

1. ZH

• 2021 ZH1
• 2020 ZH1
• 2019 ZH1
• 2018 ZH1

2. ZH

• 2020 ZH2
• 2019 ZH2
• 2018 ZH2

Régi tárgy

1. ZH

• 2016 ZH1 Nem hivatalos megoldás
• 2015 ZH1 Nem hivatalos megoldás
• 2014 ZH1 Nem hivatalos megoldás
• 2013 ZH1 Nem hivatalos megoldás
• 2012 ZH1
• 2011 ZH1-ZH2
• 2010 ZH1
• 2009 ZH1

2. ZH

• 2016 ZH2
• 2015 ZH2
• 2014 ZH2
• Nem hivatalos feladat megoldások 2.ZH témaköréből
• 2013 ZH2
• 2012 ZH2
• 2011 ZH2
• 2011 ZH1-ZH2
• 2010 ZH2
• 2009 ZH2

3. ZH

• 2015 ZH3
• 2014 ZH3
• Nem hivatalos feladat megoldások 3.ZH témaköréből
• 2013 ZH3
• 2012 ZH3
• 2011 ZH3
• 2010 ZH3
• 2009 ZH3

Régi 4. zh-k

• Nem hivatalos feladat megoldások 4.ZH témaköréből
• 2013 ZH4
• 2012 ZH4
• 2011 ZH4
• 2010 ZH4
• 2009 ZH4

Mérnökinformatikus MSc
1. félév (tavasz)	Adatbiztonság  •  Formális módszerek  •  Rendszeroptimalizálás  •  Analízis  •  Tömegkiszolgálás
2. félév (ősz)	Alkalmazott algebra és matematikai logika  •  Információelmélet  •  Nyelvek és automaták  •  Szoftverarchitektúrák  •  Sztochasztika I.  •  Sztochasztika II.
Egyéb	Kötelezően választható tárgyak  •  Mérnöki menedzsment  •  Befektetések  •  Érvelés, tárgyalás, meggyőzés  •  Információs társadalom joga  •  Minőségmenedzsment  •  Projektmenedzsment  •  Vállalati jog  •  Vezetői számvitel
Szakirányok	Alkalmazott informatika  •  Autonóm irányító rendszerek és robotok  •  Hálózatok és szolgáltatások  •  Hírközlő rendszerek biztonsága  •  Intelligens rendszerek  •  Médiainformatika  •  Rendszerfejlesztés  •  Számításelmélet  •  Szolgáltatásbiztos rendszertervezés