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

A VIK Wikiből
Ugrás a navigációhoz Ugrás a kereséshez
 
(38 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 = 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===
29. 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===
47. 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_2014_gyak12_feladat.pdf|Turing-gép]] || [[Média:Nyau_2014_gyak12_megoldasok.pdf|Turing-gép - 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_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_9_veremautomatak.pdf‎|Veremautomaták]] || Veremautomaták - 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_10_cf_pda.pdf‎|Veremautomaták és CF nyelvtanok]] || Veremautomaták és CF nyelvtanok - 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_gyakorlat_2014_11_cnf_cyk.pdf‎|Chomsky-normálforma, CYK algoritmus]] || Chomsky-normálforma, CYK algoritmus - 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]]
 
|}
 
|}
  
90. 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)
+
 
 +
===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.
  
−
==ZH-k==
+
===Új tárgy===
−
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.
+
====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]]  
103. 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_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 zh1 zh2 2011.jpg|2011 ZH1-ZH2]]  
−
* {{InLineFileLink|Infoszak|Nya|2010osz_zh2.zip|2010 ősz 2. ZH Feladatsor}} : 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]]
−
* {{InLineFileLink|Infoszak|Nya|09zh-2.pdf|2009 ősz 2. ZH Feladatsor}}: 2009 ZH2
+
 
−
===3. ZH===
+
====3. ZH====
−
* {{InLineFileLink|Infoszak|Nya|NyA-2011Osz-3ZH-3PZH.jpg|2011 ősz 3. ZH és 3. PZH Feladatsor}}: 2011 ZH3 PZH3
+
* [[Média:Nyau_zh3_2015.pdf|2015 ZH3]]
−
* {{InLineFileLink|Infoszak|Nya|2010osz_zh3_mo.zip|2010 ősz 3. ZH Feladatsor és Megoldás}}: 2010 ZH3
+
* [[Média:Nyau_zh3_2014_eredeti.pdf‎|2014 ZH3]]
−
* {{InLineFileLink|Infoszak|Nya|09zh-3.pdf|2009 ősz 3. ZH Feladatsor 09zh-3.pdf}}: 2009 ZH3
+
* [[Média:Nyau_zh3_2014.pdf| Nem hivatalos feladat megoldások 3.ZH témaköréből]]
−
===4. ZH===
+
* [[Média:Nyau_zh3_2013.pdf‎|2013 ZH3]]
−
* {{InLineFileLink|Infoszak|Nya|NyA-2011Osz-4ZH.jpg|2011 ősz 4. ZH Feladatsor}}: 2011 ZH4
+
* [[Média:Nyau_zh3_2012.pdf‎‎‎‎|2012 ZH3]]
−
* {{InLineFileLink|Infoszak|Nya|NyA-2011Osz-4PZH.jpg|2011 ősz 4. pótZH Feladatsor}}: 2011 PZH4
+
* [[Média:Nyau_zh3_2011.pdf‎‎‎|2011 ZH3]]
−
* {{InLineFileLink|Infoszak|Nya|nya4.jpg|2010 ősz 4. ZH és pótZH Feladatsor}}: 2010 ZH4
+
* [[Média:Nyau_zh3_2010.pdf‎‎|2010 ZH3]]
−
* {{InLineFileLink|Infoszak|Nya|09zh-4.pdf|2009 ősz 4. ZH Feladatsor 09zh-4.pdf}}: 2009 ZH4
+
* [[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}}
 
{{Lábléc - Mérnök informatikus mesterszak}}

A lap jelenlegi, 2023. január 29., 12:29-kori változata

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


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

Segédanyagok

Jegyzetek

Könyv

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

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

Gyakorlat 2010

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

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

2. ZH

3. ZH

Régi 4. zh-k
1. félév (tavasz)
2. félév (ősz)
Egyéb
Szakirányok


A lap eredeti címe: „https://vik.wiki/index.php?title=Nyelvek_és_automaták&oldid=203611”