Nyelvek és automaták

2021 ősz

A félév során lesz néhány beadható feladat, amelyekkel a zh-kból kapott pontátlagot lehet (kicsit) felfelé módosítani.



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.

Tájékoztatásul a ponthatárok:
Ha valamelyik zh-t nem teljesítette: elégtelen
Különben, ha p=a két zh pontátlaga (kerekítés nélkül!), akkor
24 ≤ p < 33: elégséges;    33 ≤ p < 42: közepes;   42 ≤ p < 51: jó;   51 ≤ p : jeles

Eredmények: mindig a kari Moodle-ban lesznek



1. zh: okt. 18. (hétfő) 18:15-19:45

Az 1. zh anyaga: az üres veremmel elfogadó veremautomaták, és minden, ami előtte volt. (Az okt.15. előadás 2. fele majd a 2. zh-ban lesz   😀 )
Vigyázat, ez nem pont az, mint ami a korábbi években volt!

Terembeosztás:  
Kezdőbetű
Terem
A-M
Q II
N-Zs
IB028

Eredmények: a kari Moodle-ban.
Tájékoztatásul: átlagpontszám: 28, legtöbb pont: 59 (gratulálok!), legkevesebb pozitív pont: 1, jegyátlag: 2,38.
A dolgozatok megnézhetők pénteken (okt.22.) az óra szünetében és az óra után, hétfőn 14 és 15 óra között a szobámban (IB137A) vagy egyéb, emailben egyeztetett időpotban.




1. pótzh: nov.3. 18:15-19:45, helyszín Q I (mindenkinek)

Anyaga: ugyanaz, mint az 1. zh anyaga

Aki nem ért el az 1.zh-n legalább 24 pontot, annak itt a lehetőség.

Aki elért annyit, az, ha akar, jöhet javítani (de kérem vagy az órán vagy emailben jelezze a szándékát).
Figyelem, aki bead dolgozatot, annál a pótzh eredménye felülírja az esetleges zh-eredményét -- kivéve, ha az 1.pótzh-n nem éri el a 24 pontot, de az 1.zh-n volt legalább 24 pontja. Ebben az esetben a pontszám nem az 1.pótzh eredményére, hanem 24-re csökken.

Eredmények a moodle-ban (Pontok/Grades).
 Tájékoztatásul: átlagpontszám: 33, legtöbb pont: 57 (gratulálok!), legkevesebb pozitív pont: 8, jegyátlag: 2,72.
A dolgozatok megtekinthetők a pénteki (nov.12.) óra szünetében, az óra után, vagy egyéb, emailben egyeztetett időpotban.
Az esetleges kérdésekkel keressenek meg.




2. zh: dec.9. 18:15-19:45

Az 2. zh anyaga: CF pumpálás, és minden ami utána jött.
De a korábbi fogalmakra szükség lehet, és pl. képesnek kell lenni eldönteni (és megindokolni), hogy egy nyelv a Chomsky hierarchia melyik osztályába tartozik, azaz szükség esetén regularitást bizonyítani vagy cáfolni.

Terembeosztás:  
Kezdőbetű
Terem
A-I
IB025
K-Zs
Q I

Eredmények a moodle-ban (A legalább elégséges jegyben már az esetlegesen beadott extra feladatok is benne vannak.)

 Tájékoztatásul: átlagpontszám: 34, legtöbb pont: 60 (gratulálok!), legkevesebb pozitív pont: 11, jegyátlag: 2,7.
A dolgozatok megtekinthetők kedden (dec. 14.) 15-16 óra között a tanszéken az IB137A szobában (vagy környékén)



2. pótzh: dec. 17. 10-12, helyszín: IE007 (mindenkinek)

Akinek a 2.zh-n lett legalább 24 pontja, és eljön javítani, kérem, hogy szerda (dec.15)  estig küldjön egy emailt. Köszönöm.

Aki nem írt 2. zh-t, de a pótzh-ra se tud rendesen felkészülni (és az 1. zh-n átment), jöhet egyből a pótpótzh-ra, nem kell a pótzh-n megjelenni. Ehhez szintén küldjön egy emailt , és ne felejtsen el jelentkezni a neptunban a pótpótzh-ra ("Díjköteles pótlás").

Eredmények (moodle-ban) !
megtekintés (tanszéken, IB137A): dec. 17. 16:30-17:30

 Tájékoztatásul: átlagpontszám: 25, legtöbb pont: 56 (gratulálok!), legkevesebb pozitív pont: 1, jegyátlag: 2



Pótpót zh: dec. 21. 10-12 IE220
Azoknak, akiknek az egyik zh-ját pótolni kell.
A feladatsor mindenkinek a neki hiányzó zh anyagából lesz.

Erre az alkalomra a neptunban jelentkezni kell (és a szokásos díj fizetésével jár)!

Eredmények: a moodle-ban.
Megtekintés: dec. 21. 16-17:30 a tanszéken (IB137A)
Aki ezt az alkalmat kihagyja, az már csak januárban láthatja a dolgozatát.
Például az első héten: január 4. 15-16,   január 5. 11-12,   január 6. 11-13.


Gyakorló feladatsorok:  ide kerülnek (hetente).    Később megoldások is megjelennek - de az nem baj, ha valaki nem pont így oldotta meg. Kétségek esetén kérdezzenek!

  1. Véges automaták    (megoldások)    2. Minimalizálás, reguláris kifejezések    (megoldások)    3. Pumpálási lemma. Nyelvtanok    (megoldások)    4. CF nyelvtanok átalakítása    (megoldások)    5. CF nyelvek, pumpálás  (A 2. feladattól kezdve a zh utánra ajánlott!)   (megoldások)    6. Algoritmikus kérdések, CYK-algoritmus      (megoldások)    7. Turing-gépek, R, RE    (megoldások)    - 8. R, RE      (megoldások)    9. PCP. Algoritmikus kérdések    (megoldások)    10. Fordítók     (megoldások)   
11. Veremfordító, TG, tár, idő     (megoldások)   

Plusz pontért beadható feladatok (időnként bővülő lista, 1-2 hetes határidőkkel): Extra feladatok
A plusz feladatok megoldásait pdf-ben lehet elküldeni emailben, vagy papíron a tanszéken leadhatók.


 
Az elhangzott előadások fontosabb témakörei: címszavakban

Jegyzet  az előadáshoz.
Kiegészítés a CYK algoritmushoz,   és a    kimenetes automatákról.  

Eddig  megtalált hibák. Aki talál még, kérem jelezze!

Nem biztos, hogy mindig pontosan a jegyzetek  alapján fogunk haladni, de a tananyag nagy részét tartalmazzák.


Egy C++ nyelvtan.

  A játékok is lehetnek nehezek.

Egy beszélt nyelv is lehet nem CF

Melyik a legnehezebb nyelv?


Korábbi zh-k
2021: 1.ZH
2020: 1.ZH      2.ZH
2019: 1.ZH      2.ZH
2018: 1.ZH      2.ZH
Még korábbi zh-k -- kicsit más tematikával (a változó VIK-es szabályok által aktuálisan meghatározott számban)
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