Nyelvek és automaták

2018 ősz



Zh-k:
A zh-kon könyv, jegyzet nem használható, mindegyik feladat 10 pontot ér (de ha van (a), (b), (c), .. része egy feladatnak, ezek nem feltétlenül érnek ugyanannyit).
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.


1. zh: október 16. (kedd) 18:15-19:45.   Terembeosztás:
Kezdőbetű
Terem
A-J
IE007
K-Zs
QI

  A zh anyaga: minden, ami az okt. 9-i előadáson vagy előbb volt.

  Eredmények: kimentek emailben, aki nem kapott, jelezze.
  Tájékoztatásul: az átlagpontszám 40, a legkisebb pozitív pontszám 4, a legnagyobb 60.

  Az okt. 26-i konzultáció idejében a dolgozatok megtekinthetők, ekkor a feladatokat is megbeszélhetjük.
 

1. pótzh: október 31. (szerda) 18:15-19:45, terem (mindenkinek): Q II
Az anyag ugyanaz, mint az 1. zh-n.
Aki javító szándékkal jön (azaz lett legalább 24 pontja a zh-n), az kérem, hogy legkésőbb okt. 28-ig jelezze.

Eredmények: kimentek emailben, aki nem kapott, jelezze. A dolgozatok a pénteki (nov.9) konzultáció alatt/után megtekinthetők.
  Tájékoztatásul: az átlagpontszám 30, a legkisebb pozitív pontszám 9, a legnagyobb 56.

2. zh: december 6.  (csütörtök)  18:15-19:45
2. pótzh: december 14. (péntek) 10:15-11:45
pótpótzh: december 19. (szerda) 10:15-11:45 (?)



Gyakorló feladatsorok: 1. Véges automaták  2. Minimálautomata, műveletek   3. Reguláris nyelvek, kifejezések, pumpálás   4. Nyelvtanok, reguláris nyelvtanok   5. CF nyelvtanok, CF pumpálás   6. CF nyelvek, Cocke-Younger-Kasami-algoritmus   7. Chomsky-normálforma; Turing-gépek     8. R, RE, Rice-tétel   9. Dominó, PCP és CF-es eldönthetőségek   10. Chomsky 0. és 1. osztály, Moore-automaták  



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

A plusz feladatok megoldásai papíron a tanszéken vagy az előadáson (az elején) adhatók be, vagy pdf-ben el lehet őket küldeni emailben.
 
Az elhangzott előadások fontosabb témakörei: címszavakban

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

Nem biztos, hogy mindig pontosan a jegyzet  alapján fogunk haladni, de a tananyag nagy része benne van.


Egy C++ nyelvtan

Egy beszélt nyelv is lehet nem CF

Melyik a legnehezebb nyelv?


Korábbi zh-k (Mivel a tananyag és a zh-k száma is változik, ezért 2018-ban a feladatok témája és száma is eltérhet a krábbiaktól.)

2017: 1.ZH     2.ZH     3.ZH
2016: 1.ZH     2.ZH     3.ZH
2015: 1.ZH     2.ZH     3.ZH    
2014: 1.ZH     2.ZH     3.ZH     4.ZH
2013: 1. ZH    2. ZH    3. ZH    4. ZH
2012: 1. ZH    2. ZH    3. ZH    4. ZH
2011: 1. ZH    2. ZH    3. ZH    4. ZH   
2010: 1. ZH    2. ZH    3. ZH    4. ZH   
2009: 1. ZH    2. ZH    3. ZH    4. ZH  



Friedl Katalin, BME   VIK   SZIT