Nyelvek és automaták

2013 ősz

Előadás: minden héten hétfőn 10-12-ig, az IB025-ben, páratlan tanítási héten pénteken (azaz szeptember 13-án és 27-én, október 25-én, november 8-án és december 6-án) 8-10-ig is, szintén az IB025-ben
Előadó: Csima Judit, IB136/b, email, weboldal
Konzultáció: pénteken 12.15-kor a QBF10-ben (mostantól mindig). Ez nem kötelező, a 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: 4 darab 50 pontos zh lesz, ezeken az anyaghoz kapcsolódó feladatokat kell megoldani. (Hasonló feladatok lesznek a kiadott gyakorló feladatsorokban.)
- Mindegyik zh-t teljesíteni kell az aláíráshoz, a zh 20 ponttó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 is (pótpótzh).
- A négyből legalább kettő zh-t mindenféle pótlás nélkül teljesíteni kell.

Gyakorló feladatsorok: 1. Véges automaták 2. Nemdeterminisztikus VA-k 3. Minimalizálás, konkatenálás 4. Pumpálás, reguláris kifejezések 5. Nyelvtanok 6. Reguláris és CF nyelvtanok 7. CF nyelvtanok átalakításai, egyértelműség 8. CF pumpálás 9. CNF, CYK 10. Veremautomata 11. Veremautomaták és CF nyelvtanok 12. Turing-gépek 13. Számoló TG, TG-ek kódolása 14. Nevezetes nyelvek, R, RE 15. R, RE, Rice-tétel, PCP 16. CF-es eldönthető dolgok, tár, idő

Plusz pontért beadható feladatok: itt (A feladatsor folyamatosan bővül.)
A megoldások papíron a tanszéken adhatók be, vagy valamilyen olvasható formában el lehet őket küldeni emailben.

Zh-k:

1. zh : október 7.
1. pótzh: október 21.
2. zh: október 28.
2. pótzh: november 11.
3. zh: november 18.
3. pótzh: december 5.
4. zh: december 9.
4. pótzh: december 16.

pótpót alkalom: december 20., , Eredmények i tt (a megfelelő zh pótzh rovatát kell nézni, oda írtam be a pontokat)
megtekintés dec. 20., péntek 14.30, IB 136/b

A zh-kon könyv, jegyzet nem használható. Összetűzött üres papírokat hozzanak, egy lapra több feladat megoldását is rá szabad írni.
Általában az összes megoldás ráférnek két oldalra, így 2-3 lapnál többre nem igazán van szükség.
A megoldásokat indokolni kell, kivéve, ha valami tanult eljárást használnak.

Tájékoztatásul a ponthatárok (feltéve, hogy minden zh megvan és legalább kettő az eredeti zh-n lett meg).
Nincs felfelé kerekítés, a jegyhez ténylegesen el kell érni az alsó határt!

pont	jegy
20 ≤ p < 27	2
27 ≤ p < 34	3
34 ≤ p < 41	4
41 ≤ p ≤ 50	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.

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

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

Csima Judit, BME VIK SZIT