Nyelvek és automaták

2018 ősz

Előadás: kedd 10-12, IE007 és páratlan tanítási héten (9/6, 10/4, 10/13 !!, 10/18, 11/15, 11/29) Cs 10-12, IE007 is.
Előadó: Friedl Katalin, IB137/A, email, weboldal
Konzultáció: P 14-16 IB134. A gyakorló feladatok és egyéb, az anyaghoz kapcsolódó kérdések megbeszélésére -- azok számára, akik igénylik. Az okt. 26-i alkalommal az 1. zh-t beszéljük meg (nem lesznek új feladatok).

Számonkérés: Két 90 perces zh lesz (a korábbi három 60 perces helyett. 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.
- Mindegyik zh-t teljesíteni kell a legalább elégséges jegyhez, a zh 40%-tól sikeres.
- A félévi jegy a zh-pontszámok átlagából (kerekítés nélkül!) keletkezik.
- Minden zh a hozzá tartozó pótzh-n pótolható/javítható.
- Ezen felül az egyik zh pótolható (de nem javítható) a pótlási héten is (pótpótzh).

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