Nyelvek és automaták

2014 ősz

Előadás: minden héten hétfőn 12-14-ig, az IB027-ben, páratlan tanítási héten pénteken (azaz szeptember 12-én és 26-án, október 18-án (október 24 helyett, szombat!!!), november 7-én és december 5-én) 8-10-ig is, szintén az IB027-ben
Előadó: Csima Judit, IB136/b, email, weboldal
Konzultáció: pénteken 12.15-kor (IB 134). 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 40 pontos zh lesz, ezeken az anyaghoz kapcsolódó feladatokat kell megoldani, illetve egy, az órai anyagot számonkérő elméleti kérdésre kell válaszolni. (Hasonló feladatok lesznek a kiadott gyakorló feladatsorokban.)
- Mindegyik zh-t teljesíteni kell az aláíráshoz, a zh 16 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 az eredeti zh időpontban, pótlás nélkül kell teljesíteni.

Gyakorló feladatsorok: 1. Véges automaták 2. Nemdeterminisztikus és epszilonos véges automata 3. Nyelvi műveletek, minimalizálás 4. Pumpálás, reguláris kifejezések 5. Reguláris nyelvek általában 6. Nyelvtanok 7. CF nyelvtanok átalakításai, egyértelműség 8. CF pumpálás 9. Veremautomaták 10. CF nyelvtanok és veremautomaták 11. Chomsky normálforma, CYK algoritmus 12. Turing gép 13. k-szalagos Turing-gép 14. Kiszámolós TG, nevezetes nyelvek, R, RE 15. R, RE, nevezetes nyelvek 16. Rice tétel, PCP 17. Nyelvtanok és TG-ek 18. Tár- és időbonyolultság

Zh-k:

1. zh : október 6. Eredmények: itt
1. pótzh: október 20. Eredmények: itt
2. zh: október 27. 18.15 - 19.15 Eredmények: itt
2. pótzh: november 10. Eredmények: itt
3. zh: november 17. Eredmények: itt
3. pótzh: december 4., Eredmények itt
4. zh: december 8. Eredmények: itt
4. pótzh: december 15. Eredmények: itt
pótpót zh: december 19., Eredmények: itt Megtekintés december 19-én, 14.00, IB 136/b vagy írjanak emailt.

A zh-kon könyv, jegyzet nem használható. 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.
Mindegyik feladat 10 pontot ér.

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
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.

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

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 kissé el fognak térni a fentiektől: várhatóan három, a fenti zhk feladataihoz hasonló feladatot kell megoldani bennük és egy, az órai agyaghoz kapcsolódó elméleti kérdést kell megválaszolni (definíció felidézése, tétel kimondása, rövid bizonyítás vagy tanult konstrukció leírása.)

Csima Judit, BME VIK SZIT