A InfoWiki wikiből
Formális Nyelvek és Automaták - Vizsgatematika
Ábécék, szavak, formális nyelvek. Műveletek szavakkal és nyelvekkel, a műveletek tulajdonságai. Generatív grammatikák, levezetések. Generatív grammatikák Chomsky-féle osztályozása. Extended Bachus-Naur forma, szintaxisdiagram.
Véges automaták matematikai definíciója, konfigurációja, az elfogadás definíciója, és a definíció értelmezése. Baar-Hillel lemma, bizonyítása, következményei. A veremautomata működésének elemzése, a delta leképezés megadása veremautomata esetén. Turing-gépek, működésük, az általuk felismert nyelvek. Környezetfüggetlen nyelvek. Levezetési fa (szintaxisfa), elemzési stratégiák.