Nyelvek és automaták (VISZMA12)

2025 ősz

Ugyanez a matematikusoknak Elméleti számítástudomány   néven fut (a korábbi ilyen nevű tantárgy utódja), az órák, számonkérések közösek.

• Előadás:  szerda 8-10,   QBF09 és páratlan tanítási héten  Cs 10-12,  IB027 is.
• Előadó: Friedl Katalin,  IB137/A, email, weboldal
  
• Konzultáció:  Igény esetén
• Számonkérés:
  Két 90 perces 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.
  
  • Mindegyik zh-n legalább 40%-ot el kell érni a legalább elégséges jegyhez.
  • A félévi jegy a zh-pontszámok összegéből keletkezik.
  • Minden zh a hozzá tartozó pótzh-n pótolható/javítható.
  • Nincs pótpótzh alkalom!

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.

Az 1. zh anyaga: Az okt. 15-i előadás végéig. Azaz Turing-gépek már nem, de addig minden.

Eredmények: a kari Moodle-ban.
Tájékoztatásul: átlagpontszám:40, legtöbb pont: 60 (gratulálok!), legkevesebb pozitív pont: 5 jegyátlag: 3,4.
A dolgozatok megnézhetők a szerdai és csütörötki óra előtt/után és (korlátozottan) az órák szünetében is. Továbbá egyéb, emailben egyeztetett időpotban.

Anyaga: ugyanaz, mint az 1. zh anyaga.

Aki jönni akar, kérem jelezze (pl. teams vagy email)

Aki nem ért el az 1.zh-n legalább 24 pontot, annak ebben a félévben ez a lehetőség maradt ezt bepótolni.

Aki elért annyit, az, ha akar, jöhet javítani. Figyelem, aki ír 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.
Tájékoztatásul: átlagpontszám: 32, legtöbb pont: 57 (gratulálok!), legkevesebb pozitív pont: 3, jegyátlag: 2,6.
A dolgozatok megtekinthetők a szerdai (nov. 26.) előadás után, esetleg a szünetben, vagy egyéb, egyeztetett időpotban.
Az esetleges kérdésekkel keressenek meg.

  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. Nyelvtanok, CF nyelvek    (megoldások)    5. Veremautomata, CYK algoritmus     (megoldások)    6. Algoritmikus kérdések    (megoldások)    7. Turing-gép, diagonális nyelv    (megoldások)    8. R, RE, Rice-tétel      (megoldások)    9. Dominó, PCP, CF eldönthetetlenség    (megoldások)    10. Idő és tár   

Plusz pontért beadható feladatok (időnként bővülő lista, 1-2 hetes határidőkkel): Extra feladatok Új!! SŐT!

Az extra feladatok megoldásait pdf-ben lehet elküldeni emailben vagy papíron az előadás elején beadhatók (vagy korábban is a tanszéki adminisztrációban).

Egy python és egy C nyelvtan.

  A játékok is lehetnek nehezek.

☺Egy beszélt nyelv is lehet nem CF

☺Melyik a legnehezebb nyelv?