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.

  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   

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

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?