„Nyelvek és automaták” változatai közötti eltérés
a |
|||
(63 közbenső módosítás, amit 11 másik szerkesztő végzett, nincs mutatva) | |||
1. sor: | 1. sor: | ||
− | {{Tantárgy|nev=Nyelvek és | + | {{Tantárgy |
+ | |nev=Nyelvek és automaták | ||
+ | |tárgykód = VISZMA04 | ||
+ | |kredit=4 | ||
+ | |felev=Őszi | ||
+ | |kiszh= | ||
+ | |vizsga=nincs | ||
+ | |nagyzh=2 db | ||
+ | |hf=opcionális | ||
+ | |szak=infoMSC | ||
+ | |levlista=infomscATsch.bme.hu | ||
+ | |tad=https://www.vik.bme.hu/kepzes/targyak/VISZM104/ | ||
+ | |targyhonlap=http://cs.bme.hu/nyau/ | ||
+ | }} | ||
+ | |||
+ | ==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== | ==Hasznos Infók== | ||
− | * Előadó: | + | * Előadó: Friedl Katalin (2021) |
− | * A tárgy ötéves megfelelője | + | * A tárgy ötéves megfelelője: [[Formális nyelvek]] |
− | + | ||
==Segédanyagok== | ==Segédanyagok== | ||
===Jegyzetek=== | ===Jegyzetek=== | ||
− | * | + | * '''[http://www.cs.bme.hu/~friedl/nyau/jegyzet-13.pdf Hivatalos jegyzet]''' |
+ | * [[:File:nyau_peabe.pdf|Gépelt Peabe-jegyzet (100% TL;DR) 2020 ősz]] | ||
+ | * [[Média:Nyau_jegyzet_2010.pdf|Legépelt jegyzet 2010 ősz]] | ||
+ | * [[Média:Nyau_kieg_2017_CYK_Algo.pdf|Kiegészítő anyag 2017 - CYK algoritmus]] | ||
+ | |||
===Könyv=== | ===Könyv=== | ||
− | * Formális nyelvek (Bach Iván) | + | * [[Média:Nyau_konyv_2002.pdf|Formális nyelvek (Bach Iván)]] |
− | |||
* Algoritmusok (Ivanyos Gábor; Szabó Réka; Rónyai Lajos) | * Algoritmusok (Ivanyos Gábor; Szabó Réka; Rónyai Lajos) | ||
− | ===Gyakorlat | + | |
+ | ==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=== | ||
+ | * [[:File:nyau_gyak1.pdf|1. Véges automaták]] | ||
+ | * [[:File:nyau_gyak2.pdf|2. Minimálautomata, reguláris kifejezés]] | ||
+ | * [[:File:nyau_gyak3.pdf|3. Pumpálási lemma. Nyelvtanok]] | ||
+ | * [[:File:nyau_gyak4.pdf|4. CF nyelvtanok átalakítása]] | ||
+ | * [[:File:nyau_gyak5.pdf|5. CF nyelvek, pumpálás]] | ||
+ | * [[:File:nyau_gyak6.pdf|6. Algoritmikus kérdések, CYK algoritmus]] | ||
+ | * [[:File:nyau_gyak7.pdf|7. Turing-gépek, R, RE]] | ||
+ | * [[:File:nyau_gyak8.pdf|8. R, RE]] | ||
+ | * [[:File:nyau_gyak9.pdf|9. PCP. Algoritmikus kérdések]] | ||
+ | * [[:File:nyau_gyak10.pdf|10. Fordítók]] | ||
+ | * [[:File:nyau_gyak11.pdf|11. Veremfordító, függvényt számoló Turing-gép. Idő és tár]] | ||
+ | |||
+ | ===Gyakorlat 2017=== | ||
+ | |||
+ | [[Média:Nyau_gyak_2017.zip | Gyakorlati anyag 2017]] | ||
+ | |||
+ | [[Média:Nyau_szorgalmi_2017.pdf| Szorgalmi, nehéz feladatok 2017]] | ||
+ | |||
+ | ===Gyakorlat 2014=== | ||
{| border="1" | {| border="1" | ||
| '''Feladatok''' || '''Megoldás''' | | '''Feladatok''' || '''Megoldás''' | ||
|- | |- | ||
− | | | + | | [[Média:Nyau_gyakorlat_2014_1_va.pdf|Véges automaták]] || [[Média:Nyau_2014_gyak1_megoldasok.pdf|Véges automaták - megoldások]] |
|- | |- | ||
− | | | + | | [[Média:Nyau_gyakorlat_2014_2_nva.pdf|Nemdeterminisztikus véges automaták]] || [[Média:Nyau_2014_gyak2 megoldasok.pdf|Nemdeterminisztikus véges automaták - megoldások]] |
|- | |- | ||
− | | | + | | [[Média:Nyau_gyakorlat_2014_3_min.pdf|Minimalizálás]] || Minimalizálás - megoldások |
|- | |- | ||
− | | | + | | [[Média:Nyau_gyakorlat_2014_4_pump.pdf|Pumpálás]] || Pumpálás - megoldások |
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2014_5_reg_nyelv.pdf|Reguláris nyelvek]] || Reguláris nyelvek - megoldások | ||
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2014_6_nyelvtan.pdf|Nyelvtanok]] || Nyelvtanok - megoldások | ||
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2014_7_cf_nyelvtanok.pdf|CF nyelvtanok átalakításai, egyértelműség]] || [[Média:Nyau_2014_gyak7_megoldasok.pdf|CF nyelvtanok átalakításai, egyértelműség - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2014_8_cf_pumpa.pdf|CF pumpálás]] || [[Média:Nyau_2014_gyak8_megoldasok.pdf|CF pumpálás - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2014_9_veremautomatak.pdf|Veremautomaták]] || [[Média:Nyau_2014_gyak9_megoldasok.pdf|Veremautomaták - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2014_10_cf_pda.pdf|Veremautomaták és CF nyelvtanok]] || [[Média:Nyau_2014_gyak10_megoldasok.pdf|Veremautomaták és CF nyelvtanok - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2014_11_cnf_cyk.pdf|Chomsky-normálforma, CYK algoritmus]] || [[Média:Nyau_2014_gyak11_megoldasok.pdf|Chomsky-normálforma, CYK algoritmus - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_2014_gyak12_feladat.pdf|Turing-gép]] || [[Média:Nyau_2014_gyak12_megoldasok.pdf|Turing-gép - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_2014_gyak13_feladat.pdf|k-szalagos Turing-gép]] || [[Média:Nyau_2014_gyak13_megoldasok.pdf|k-szalagos Turing-gép - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_2014_gyak14_feladat.pdf|Kiszámolós TG, nevezetes nyelvek, R, RE]] || [[Média:Nyau_2014_gyak14_megoldasok.pdf|Kiszámolós TG, nevezetes nyelvek, R, RE - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_2014_gyak15_feladat.pdf|R, RE, Nevezetes nyelvek]] || [[Média:Nyau_2014_gyak15_megoldasok.pdf|R, RE, Nevezetes nyelvek - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_2014_gyak16_feladat.pdf|Rice tétel, PCP]] || [[Média:Nyau_2014_gyak16_megoldasok.pdf|Rice tétel, PCP - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_2014_gyak17_feladat.pdf|Nyelvtanok és TG-ek]] || [[Média:Nyau_2014_gyak17_megoldasok.pdf|Nyelvtanok és TG-ek - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_2014_gyak18_feladat.pdf|Tár- és időbonyolultság]] || [[Média:Nyau_2014_gyak18_megoldasok.pdf|Tár- és időbonyolultság - megoldások]] | ||
+ | |} | ||
+ | |||
+ | ===Gyakorlat 2012=== | ||
+ | |||
+ | {| border="1" | ||
+ | | '''Feladatok''' || '''Megoldás''' | ||
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2012_1_va.pdf|Véges automaták]] || [[Média:Nyau_gyakorlat_2012_1_va_megoldasok.pdf|Véges automaták, Nemdeterminisztikus véges automaták - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2012_2_nva.pdf|Nemdeterminisztikus véges automaták]] || [[Média:Nyau_gyakorlat_2012_1_va_megoldasok.pdf|Véges automaták, Nemdeterminisztikus véges automaták - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2012_3_min.pdf|Minimalizálás]] || [[Média:Nyau_gyakorlat_2012_3_min_4_pump_megoldasok.pdf|Minimalizálás, Pumpálás - megoldások]] | ||
+ | |- | ||
+ | | [[Média:Nyau_gyakorlat_2012_4_pump.pdf|Pumpálás]] || [[Média:Nyau_gyakorlat_2012_3_min_4_pump_megoldasok.pdf|Minimalizálás, Pumpálás - megoldások]] | ||
|} | |} | ||
===Gyakorlat 2011=== | ===Gyakorlat 2011=== | ||
− | * | + | * [[Média:NyA-2011Osz-Gyakorlat-Feladatok.zip|NyA-2011Osz-Gyakorlat-Feladatok.zip]] |
− | * | + | * [[Média:nyau_3.zip|2011. 3 ZH előtti gyakorlatok]] |
+ | |||
===Gyakorlat 2010=== | ===Gyakorlat 2010=== | ||
(Nem hivatalos megoldások, tehát tartalmazhatnak hibát, csak saját felelősségre!) | (Nem hivatalos megoldások, tehát tartalmazhatnak hibát, csak saját felelősségre!) | ||
− | * 1. gyakorlat (2010.09.09) | + | * 1. gyakorlat (2010.09.09) [[Média:Nya-g-10o-1-va.pdf|Feladatsor]] |
− | * 2. gyakorlat (2010.09.16) | + | * 2. gyakorlat (2010.09.16) [[Média:Nya-g-10o-2-va.pdf|Feladatsor]] [[Média:Nya-m-10o-2.pdf|Megoldás]] |
− | * 3. gyakorlat (2010.09.23) | + | * 3. gyakorlat (2010.09.23) [[Média:Nya-g-10o-3-rkif.pdf|Feladatsor]] [[Média:Nya-m-10o-3.pdf|Megoldás]] |
− | * 4. gyakorlat (2010.09.30) | + | * 4. gyakorlat (2010.09.30) [[Média:Nya-g-10o-4-nyelvtan.pdf|Feladatsor]] [[Média:Nya-m-10o-4.pdf|Megoldás]] |
− | * 5. gyakorlat (2010.10.14) | + | * 5. gyakorlat (2010.10.14) [[Média:Nya-g-10o-5-verem.pdf|Feladatsor]] [[Média:Gyak05.zip|Megoldás]] |
− | * 6. gyakorlat (2010.10.21) | + | * 6. gyakorlat (2010.10.21) [[Média:Nya-g-10o-6-cyk.pdf|Feladatsor]] [[Média:Gyak06.zip|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) | + | * 7. gyakorlat (2010.10.28) [[Média:Nya-g-10o-6-cyk.pdf|Feladatsor]] [[Média:Gyak07.zip|Megoldás]] |
− | * 8. gyakorlat (2010.11.04) | + | * 8. gyakorlat (2010.11.04) [[Média:Nya-g-10o-7-cfpump.pdf|Feladatsor]] [[Média:Gyak08.zip|Megoldás]] |
− | * 9. gyakorlat (2010.11.11) | + | * 9. gyakorlat (2010.11.11) [[Média:Nya-g-10o-8-re.pdf|Feladatsor]] [[Média:Gyak09.zip|Megoldás]] (Frissült 2010.12.04-én) |
− | * 10. gyakorlat (2010.11.18) | + | * 10. gyakorlat (2010.11.18) [[Média:Nya-g-10o-9-rice.pdf|Feladatsor]] [[Média:Gyak10.zip|Megoldás]] |
− | * 11. gyakorlat (2010.11.25) | + | * 11. gyakorlat (2010.11.25) [[Média:Nya-g-10o-9-rice.pdf|Feladatsor]] [[Média:Gyak11.zip|Megoldás]] |
− | * 12. gyakorlat (2010.12.02) | + | * 12. gyakorlat (2010.12.02) [[Média:Nya-g-10o-10-ido.pdf|Feladatsor]] [[Média:Gyak12.zip|Megoldás]] |
− | + | ||
− | |||
− | |||
==ZH-k== | ==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. | |
− | + | ||
− | + | ===1. ZH tippek=== | |
− | + | ||
− | + | ===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==== | |
− | + | * [[:File:nyau_zh1_2021.pdf|2021 ZH1]] | |
− | === | + | * [[:File:nyau_zh1_2020.pdf|2020 ZH1]] |
− | + | * [[:File:nyau_zh1_2019.pdf|2019 ZH1]] | |
− | + | * [[:File:nyau_zh1_2018.pdf|2018 ZH1]] | |
− | |||
− | === | ||
− | * | ||
− | * | ||
− | * | ||
− | * | ||
+ | ====2. ZH==== | ||
+ | * [[:File:nyau_zh2_2020.pdf|2020 ZH2]] | ||
+ | * [[:File:nyau_zh2_2019.pdf|2019 ZH2]] | ||
+ | * [[:File:nyau_zh2_2018.pdf|2018 ZH2]] | ||
+ | ===Régi tárgy=== | ||
+ | ====1. ZH==== | ||
+ | * [[Média:Nyau_zh1_2016.pdf |2016 ZH1]] [[Média:Nyau_zh1_2016_mo.docx |Nem hivatalos megoldás]] | ||
+ | * [[Média:Nyau_zh1_2015.pdf |2015 ZH1]] [[Média:Nyau_zh1_2015_mo.docx |Nem hivatalos megoldás]] | ||
+ | * [[Média:Nyau_zh1_2014.pdf |2014 ZH1]] [[Média:Nyau_zh1_2014_mo.docx |Nem hivatalos megoldás]] | ||
+ | * [[Média:Nyau_zh1_2013.pdf |2013 ZH1]] [[Média:Nyau_zh1_2013_mo.docx |Nem hivatalos megoldás]] | ||
+ | * [[Média:Nyau_zh1_2012.jpg|2012 ZH1]] | ||
+ | * [[Média:Nyau_zh1_zh2_2011.jpg|2011 ZH1-ZH2]] | ||
+ | * [[Média:Nyau_zh1_2010.jpg|2010 ZH1]] | ||
+ | * [[Média:Nyau_zh1_2009.pdf|2009 ZH1]] | ||
+ | ====2. ZH==== | ||
+ | * [[Média:Nyau_zh2_2016.pdf |2016 ZH2]] | ||
+ | * [[Média:Nyau_zh2_2015.pdf |2015 ZH2]] | ||
+ | * [[Média:Nyau_zh2_2014_eredeti.pdf |2014 ZH2]] | ||
+ | * [[Média:Nyau_zh2_2014.pdf| Nem hivatalos feladat megoldások 2.ZH témaköréből]] | ||
+ | * [[Média:Nyau_zh2_2013.pdf|2013 ZH2]] | ||
+ | * [[Média:Nyau_zh2_2012.pdf|2012 ZH2]] | ||
+ | * [[Média:Nyau_zh2_2011.pdf|2011 ZH2]] | ||
+ | * [[Média:Nyau zh1 zh2 2011.jpg|2011 ZH1-ZH2]] | ||
+ | * [[Média:Nyau_zh2_2010.pdf|2010 ZH2]] | ||
+ | * [[Média:Nyau_zh2_2009.pdf|2009 ZH2]] | ||
− | + | ====3. ZH==== | |
+ | * [[Média:Nyau_zh3_2015.pdf|2015 ZH3]] | ||
+ | * [[Média:Nyau_zh3_2014_eredeti.pdf|2014 ZH3]] | ||
+ | * [[Média:Nyau_zh3_2014.pdf| Nem hivatalos feladat megoldások 3.ZH témaköréből]] | ||
+ | * [[Média:Nyau_zh3_2013.pdf|2013 ZH3]] | ||
+ | * [[Média:Nyau_zh3_2012.pdf|2012 ZH3]] | ||
+ | * [[Média:Nyau_zh3_2011.pdf|2011 ZH3]] | ||
+ | * [[Média:Nyau_zh3_2010.pdf|2010 ZH3]] | ||
+ | * [[Média:Nyau_zh3_2009.pdf|2009 ZH3]] | ||
+ | ====Régi 4. zh-k==== | ||
+ | * [[Média:Nyau_zh4_2014.pdf| Nem hivatalos feladat megoldások 4.ZH témaköréből]] | ||
+ | * [[Média:Nyau_zh4_2013.pdf|2013 ZH4]] | ||
+ | * [[Média:Nyau_zh4_2012.pdf|2012 ZH4]] | ||
+ | * [[Média:Nyau_zh4_2011.pdf|2011 ZH4]] | ||
+ | * [[Média:Nyau_zh4_2010.pdf|2010 ZH4]] | ||
+ | * [[Média:Nyau_zh4_2009.pdf|2009 ZH4]] | ||
− | + | {{Lábléc - Mérnök informatikus mesterszak}} |
A lap jelenlegi, 2023. január 29., 12:29-kori változata
Tartalomjegyzék
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
Szorgalmi, nehéz feladatok 2017
Gyakorlat 2014
Gyakorlat 2012
Gyakorlat 2011
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.
1. ZH tippek
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
2. ZH
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
1. félév (tavasz) | |
---|---|
2. félév (ősz) | |
Egyéb | |
Szakirányok |