Nyelvek és automaták

2015 ősz

Előadás: minden héten hétfőn 12-14-ig, az IE007-ben, továbbá páratlan tanítási héten csütörtökön (azaz szeptember 10-én és 24-én, október 22-én, november 5-én és 19-én és december 3-án) 10-12-ig, az IB026-ban
Előadó: Csima Judit, IB136/b, email, weboldal
Konzultáció: csütörtökön 12.15-kor az IB134-ben. Ez nem kötelező, a kiadott gyakorló feladatok és egyéb, az anyaghoz kapcsolódó kérdések megbeszélésére van -- azok számára, akik igénylik.

Számonkérés: Három zh lesz, 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. (Hasonló feladatok lesznek a kiadott gyakorló feladatsorokban.)
- Mindegyik zh-t teljesíteni kell az aláíráshoz, a zh 40%-tól sikeres.
- A félévi jegy a zh-pontszámok átlaga alapján keletkezik.
- Minden zh a hozzá tartozó pótzh-n pótolható/javítható.
- Egy zh pótolható ezen felül a pótlási héten (pótpótzh).

Gyakorló feladatsorok: 1.Véges automaták, műveleti zártság 2. Nemdeterminisztikus VA 3. Konkatenálás, tranzitív lezárt; Minimálautomata 4. Pumpálási lemma 5. Reguláris kifejezések, általános nyelvtanok 6. Reguláris nyelvtanok 7. CF nyelvtanok átalakításai, CF pumpálás 8. Ogden-lemma, CF zártság 9. Veremautomata 10. CNF, CYK, egyértelműség 12. Turing-gép 13. k-szalagos TG 14. Számolós TG, nevezetes nyelvek 15. Nevezetes nyelvek, R, RE 16. R, Re, Rice tétel 17. PCP, CF-es eldönthetőség 18. Idő- és tárkorlát

Plusz pontért beadható feladatok: hétről hétre bővül, feladatsor itt

A megoldások papíron a tanszéken adhatók be, vagy pdf-ben el lehet őket küldeni emailben.

Zh-k:

1. zh : október 6. , eredmények itt
1. pótzh: október 22., eredmények itt
2. zh: november 5. eredmények itt
2. pótzh: november 13., eredmények itt
3. zh: december 3. Eredmények: itt (A zh eredménye és a félévi jegy is.)
3. pótzh: december 15., Eredmények: itt

pótpót zh: december 18., 12.15-13.15, Eredmények: itt Megtekintés hétfőn 9.30-kor az IB136/b-ben.

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

A Python nyelvntanáról és a természetes nyelvekről vetített rövid prezentáció

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.

További gyakorlási lehetőség:

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 kicsit másmilyenek lesznek, mint az eddigiek. Várhatóan 5 feladatot tartalmaznak, mint a 2014 előtti zh-k, de lesz bennük elmélet is, mint a 2014-es zhkban.

Csima Judit, BME VIK SZIT