Nyelvek és automaták

2017 ősz

Előadás: minden héten szerdán 10-12-ig, az IE007-ben, továbbá páros tanítási héten csütörtökön 10-12-ig, szintén az IE007-ben
Előadó: Csima Judit, IB136/b, email, weboldal
Konzultáció: A december 1. és december 8-i, pénteki konzultációt (12-14, QBF10) akkor tartjuk meg, ha erre van igény, ezt jelezzék Kabódi Lacinak.

Számonkérés: Három 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. (Hasonló lesz, mint amilyenek a tavalyi és tavaly előtti zhk voltak.)
- Mindegyik zh-t teljesíteni kell az aláíráshoz, a zh 40%-tól sikeres.
- A félévi jegy a zh-pontszámok átlaga alapján keletkezik.
- Minden zh a hozzá tartozó pótzh-n pótolható/javítható.
- Egy zh pótolható ezen felül a pótlási héten (pótpótzh).

Gyakorló feladatsorok: 1. Véges automaták 2. Nemdeterminisztikus véges automaták 3. Minimálautomata 4. Pumpálási lemma és reguláris kifejezések 5. Nyelvtanok 6. VA = reguláris nyelvtan, CF nyelvtanok átalakítása 7. CF pumpa, CF zártságok 8. Veremautomaták 9. Cocke-Younger-Kasami algo 10. CF nyelvtanok egyértelműsége 11. Turing-gép 12. Számolós TG 13. Nevezetes nyelvek, R és RE 14. coRE, Rice tétel 15. PCP, CF-es eldöntések, TG és nyelvtanok kapcsolatai 16. Tár és idő 17. Tár és idő még egyszer

Plusz pontért beadható feladatok (hétről hétre bővülő lista, 1-2 hetes határidőkkel): Extra feladatok

A plusz feladatok megoldásai papíron a tanszéken (vagy az órán) adhatók be, vagy pdf-ben el lehet őket küldeni emailben.

Zh-k:

1. zh: október 12. Eredmények: itt
1. pótzh: október 19., Eredmények itt
2. zh: november 9., Eredmények itt
2. pótzh: november 14., Eredmények itt
3. zh: november 30., Eredmények: itt

3. pótzh: december 13., Eredmények: itt

pótpótzh: december 18., Eredmények: itt

A zh-kon könyv, jegyzet nem használható, mindegyik feladat 10 pontot ér. A kiadott feladatlapon kell beadni a megoldásokat, ha az ezen levő hely nem lenne elég, akkor egy (vagy ha nagyon muszáj, akkor több) hozzátűzött papírlapon lehet folytatni a munkát. A megoldásokat indokolni kell, kivéve, ha valami tanult eljárást használnak, de ekkor látszódnia kell a tanult lépéseknek.

Tájékoztatásul a ponthatárok (feltéve, hogy minden zh megvan. Nincs felfelé kerekítés, a jegyhez ténylegesen el kell érni az alsó határt!

pont	jegy
16 ≤ p < 22	2
22 ≤ p < 28	3
28≤ p < 34	4
34≤ p ≤ 40	5

Az elhangzott előadások fontosabb témakörei: címszavakban

Jegyzet az előadáshoz. Kiegészítés a CYK algoritmushoz. Megtalált hibák eddig. Aki talál még benne hibát, kérem jelezze!

Nem biztos, hogy mindig pontosan ezen jegyzet alapján fogunk haladni, de nagy eltérések nem várhatóak.

Régebi zhk, gyakorlási lehetőség:

a 2016-os 1.ZH     2.ZH    3.ZH
a 2015-ös 1.ZH     2.ZH     3.ZH
a 2014-es 1.ZH     2.ZH     3.ZH     4.ZH
a 2013-as 1. ZH    2. ZH    3. ZH    4. ZH
a 2012-es 1. ZH    2. ZH    3. ZH    4. ZH
a 2011-es 1. ZH    2. ZH    3. ZH    4. ZH
a 2010-es 1. ZH    2. ZH    3. ZH    4. ZH
a 2009-es 1. ZH    2. ZH    3. ZH    4. ZH

Az idei zhk felépítése a 2014-es, 2015-ös, 2016-os zhk felépítéséhez fog hasonlítani (4 feladat, ebből egy elméleti kérdés). A korábbi zhk feladatait is érdemes azonban nézegetni, mert a kérdések szemlélete és nehézsége nem változott az évek alatt.

Csima Judit, BME VIK SZIT