Nyelvek és automaták

2016 ősz

Előadás: minden héten szerdán 10-12-ig, az IE007-ben, továbbá páratlan tanítási héten csütörtökön (amikor éppen nem marad el valami miatt, azaz szeptember 8-án és 22-én, október 20-án, november 3-án és december 1-én) 10-12-ig, szintén az IE007-ben
Előadó: Csima Judit, IB136/b, email, weboldal
Konzultáció: pénteken 12-14-ig, az IB 134-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ó lesz, mint amilyenek a tavalyi zhk voltak.)
- 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á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