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    Terembeosztás:
Kezdőbetű
Terem
A-J
IB026
K-Zs
QI

A zh anyaga: minden, ami a nov. 29-i előadáson vagy előbb volt.

Eredmények kimentek emailben, aki nem kapott, jelezze.
Megtekintés: dec.10. hétfő 14-16, valahol a tanszéken (aki nem tud jönni, de meg akarja nézni,  keressen meg emailben).

  Tájékoztatásul: az átlagpontszám 32, a legkisebb pozitív pontszám 1, a legnagyobb 60.

2. pótzh: december 14. (péntek) 10:15-11:45  IB027
Az anyag ugyanaz, mint a 2. zh-n.
Aki javító szándékkal jön (azaz lett legalább 24 pontja a 2. zh-n), az kérem, hogy legkésőbb dec.13. délig jelezze!

Segítségül felkerült az oldalra a kimenetes automatákról egy kiegészítés.

Konzultáció hétfőn 15 órától (valahol a tanszéken)

Eredmények kimentek emailben, aki nem kapott, jelezze.
Megtekintés: dec.17. hétfő 14-16, valahol a tanszéken (aki nem tud jönni, de meg akarja nézni,  keressen meg emailben).

  Tájékoztatásul: az átlagpontszám 25.5, a legkisebb pozitív pontszám 4, a legnagyobb 59.


Pótpót zh: december 19. (szerda) 10:15-11:45, QBF09
Azoknak, akiknek az egyik zh-ja nem lett meg, de a másik igen. A feladatsor mindenkinek a neki hiányzó zh anyagából lesz.
Erre az alkalomra a neptunban jelentkezni kell (Díjköteles pótlás).
Itt elégtelentől különböző jegyet már nem lehet javítani!

Eredmények kimentek emailben, aki nem kapott, jelezze.
Megtekintés: dec.20. 15-16, a tanszéken a szobámban (IB137/A)



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   11. Automaták kimenettel   11. Idő és tár  



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.

Kiegészítés a kimenetes automatákról.  (Még változhat -- aki talál benne hibát, nem érthető részt, kérem jelezze! )


Egy C++ nyelvtan.

  A játékok is lehetnek nehezek.

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