Nyelvek és automaták

2017 ősz



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

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  A dolgozatok megtekinthetők a szerdai (november 22.) előadás után az IB136/b-ben

3. zh: november 30., 18-20
3. pótzh: december 14. (?), 18-20 (?) (állítólag ez máskor lesz, de hivatalosan még nekem nem szóltak)



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 algoritmushozMegtalá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