VIK Wiki

„Nyelvek és automaták” változatai közötti eltérés

← Régebbi szerkesztés
VizuálisWikiszöveges
Nincs szerkesztési összefoglaló
 
(33 közbenső módosítás, amit 10 másik szerkesztő végzett, nincs mutatva)
1. sor: 1. sor:
{{FejlesztesAlatt}}
{{Tantárgy
{{Tantárgy
|nev=Nyelvek és automaták
|nev=Nyelvek és automaták
|tárgykód = VISZM104
|tárgykód = VISZMA04
|kredit=4
|kredit=4
|felev=Őszi
|felev=Őszi
|kiszh=
|kiszh=
|vizsga=nincs
|vizsga=nincs
|nagyzh=4 db
|nagyzh=2 db
|hf=random opcionális
|hf=opcionális
|szak=MSC info
|szak=infoMSC
|levlista=infomscATsch.bme.hu
|levlista=infomscATsch.bme.hu
|tad=https://www.vik.bme.hu/kepzes/targyak/VISZM104/
|tad=https://www.vik.bme.hu/kepzes/targyak/VISZM104/
|targyhonlap=http://cs.bme.hu/nya/
|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ó: Dr. Friedl Katalin vagy Csima Judit
* Előadó: Friedl Katalin (2021)
* A tárgy ötéves megfelelője: [[Formális nyelvek]]
* 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_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===
30. sor: 34. sor:
==Gyakorlatok==
==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.
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===
===Gyakorlat 2014===
48. sor: 71. sor:
| [[Média:Nyau_gyakorlat_2014_6_nyelvtan.pdf|Nyelvtanok]] || Nyelvtanok - 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]] || CF nyelvtanok átalakításai, egyértelműség - 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_gyakorlat_2014_8_cf_pumpa.pdf‎|CF pumpálás]] || CF pumpálás - 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_gyakorlat_2014_9_veremautomatak.pdf‎|Veremautomaták]] || Veremautomaták - 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_gyakorlat_2014_10_cf_pda.pdf‎|Veremautomaták és CF nyelvtanok]] || Veremautomaták és CF nyelvtanok - 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_gyakorlat_2014_11_cnf_cyk.pdf‎|Chomsky-normálforma, CYK algoritmus]] || Chomsky-normálforma, CYK algoritmus - 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]]
|}
|}


91. sor: 128. sor:
* 12. gyakorlat (2010.12.02) [[Média:Nya-g-10o-10-ido.pdf|Feladatsor]] [[Média:Gyak12.zip|Megoldás]]
* 12. gyakorlat (2010.12.02) [[Média:Nya-g-10o-10-ido.pdf|Feladatsor]] [[Média:Gyak12.zip|Megoldás]]


===Gyakorlat 2009 ===
==ZH-k==
* {{InLineFileLink|Infoszak|Nya|nya09f1.zip|nya09f1.zip}}: az első 2009-es feladatsor "megoldása" (itt-ott lehet hibás)
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.
* {{InLineFileLink|Infoszak|Nya|nya09f2.zip|nya09f2.zip}}: a második 2009-es feladatsor "megoldása" (itt-ott lehet hibás)


==ZH-k==
===1. ZH tippek===
4 db ZH-t kell teljesíteni a félévben, amiből kettőnek az első alkalommal sikerülnie kell, a többi pótolható, egyik kétszer is (pótót). A 4 feladatos zh-kon nagyrészt gyakorlati példákat kell megoldani, a 2014-es őszi félévtől kezdve egy elméleti kérdés (tétel, vagy definíció kimondátsa, esetleg egyszerűbb bizonyítás) 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====
* [[: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]]


===1. ZH===
===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_2012.jpg|2012 ZH1]]  
* [[Média:Nyau_zh1_zh2_2011.jpg|2011 ZH1-ZH2]]  
* [[Média:Nyau_zh1_zh2_2011.jpg|2011 ZH1-ZH2]]  
104. sor: 159. sor:
* [[Média:Nyau_zh1_2009.pdf|2009 ZH1]]
* [[Média:Nyau_zh1_2009.pdf|2009 ZH1]]


===2. ZH===
====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_2013.pdf‎|2013 ZH2]]  
* [[Média:Nyau_zh2_2012.pdf‎|2012 ZH2]]
* [[Média:Nyau_zh2_2012.pdf‎|2012 ZH2]]
110. sor: 169. sor:
* [[Média:Nyau zh1 zh2 2011.jpg|2011 ZH1-ZH2]]  
* [[Média:Nyau zh1 zh2 2011.jpg|2011 ZH1-ZH2]]  
* [[Média:Nyau_zh2_2010.pdf‎|2010 ZH2]]  
* [[Média:Nyau_zh2_2010.pdf‎|2010 ZH2]]  
* {{InLineFileLink|Infoszak|Nya|2010osz_zh2mo.zip|2010 ősz 2. ZH Megoldás}}
* [[Média:Nyau_zh2_2009.pdf|2009 ZH2]]
* [[Média:Nyau_zh2_2009.pdf|2009 ZH2]]


===3. ZH===
====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_2013.pdf‎|2013 ZH3]]
* [[Média:Nyau_zh3_2012.pdf‎‎‎‎|2012 ZH3]]
* [[Média:Nyau_zh3_2012.pdf‎‎‎‎|2012 ZH3]]
* {{InLineFileLink|Infoszak|Nya|NyA-2011Osz-3ZH-3PZH.jpg|2011 ősz 3. ZH és 3. PZH Feladatsor}}
* [[Média:Nyau_zh3_2011.pdf‎‎‎|2011 ZH3]]
* [[Média:Nyau_zh3_2011.pdf‎‎‎|2011 ZH3]]
* [[Média:Nyau_zh3_2010.pdf‎‎|2010 ZH3]]
* [[Média:Nyau_zh3_2010.pdf‎‎|2010 ZH3]]
* [[Média:Nyau_zh3_2009.pdf‎|2009 ZH3]]
* [[Média:Nyau_zh3_2009.pdf‎|2009 ZH3]]


===4. ZH===
====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_2013.pdf|2013 ZH4]]
* [[Média:Nyau_zh4_2012.pdf|2012 ZH4]]
* [[Média:Nyau_zh4_2012.pdf|2012 ZH4]]
* {{InLineFileLink|Infoszak|Nya|NyA-2011Osz-4PZH.jpg|2011 ősz 4. pótZH Feladatsor}}
* [[Média:Nyau_zh4_2011.pdf|2011 ZH4]]
* [[Média:Nyau_zh4_2011.pdf|2011 ZH4]]
* [[Média:Nyau_zh4_2010.pdf|2010 ZH4]]
* [[Média:Nyau_zh4_2010.pdf|2010 ZH4]]
A lap eredeti címe: „https://vik.wiki/Nyelvek_és_automaták”