Nyelvek és automaták

2016 ősz



Gyakorló feladatsorok:
1. Véges automaták, műveleti zártságok    2. Nemdeterminisztikus és epszilonos VA-k 3. Zártság tranzitív lezártra és konkatenáltra; Minimálautomata  4. Pumpálási lemma reguláris nyelvekre  5. Reguláris kifejezések  6. Nyelvtanok, reguláris nyelvtan és VA kapcsolata, általános regulárisos kérdések 
7. CF nyelvtanok átalakításai, CF pumpa 8. CF zártságok, veremautomata  9. CF nyelvtanból PDA  10. CNF, CYK, egyértelműség  11. Turing-gépek  12. Kiszámolós TG, R, RE, diagonális nyelv  13. R, RE  14. R. RE, Rice tétel  15. PCP, CF-es eldönthetőségek  16. Tár-idő tétel, idő- és tárosztályok
 
Plusz pontért beadható feladatok: itt (hétről hétre bővül)

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 eredménye
1. pótzh eredménye

2. zh: eredménye  
2. pótzh: eredménye
3. zh:
   eredménye 

3. pótzh eredménye  itt (
a dolgozatok megtekinthetők december 19-én hétfőn 9-10-ig az IB136/b-ben vagy ha ez nem jó, akkor írjanak emailt)

pótpót zh: eredménye itt   (a dolgozatok megtekinthetők januárban, írjanak emailt az időpont egyeztetéséhez)

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. 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 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 2015-ös és 2014-es 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