Formális nyelvek és automaták lezártsági problémái

Abstract

Szakdolgozatomban a Formális nyelvek és automaták lezártsági problémáival foglalkozom. Célom az volt, hogy az ezen a téren elért alapvető eredményekről átfogó képet adjak. A lezártsági problémákról nagyon kevés magyar nyelvű szakirodalom található, ezért a munkám jelentős részét angol nyelvű könyvek valamint cikkek segítségével készítettem el.

Egy nyelvosztály lezártsági tulajdonságainak ismeretével, könnyebben megállapíthatjuk, hogy melyik nyelv melyik nyelvosztályba tartozik. Ha van egy adott nyelvünk, melyről nem tudjuk hogy melyik nyelvosztályba tartozik, de ezt a nyelvet felbonthatjuk 2 nyelv uniójára és a két nyelvről meg tudjuk mondani hogy melyik nyelvosztályba tartoznak, valamint ismerjük a nyelvosztály unióképzésre való lezártságát, akkor az eredeti nyelvünkről is elmondhatjuk, hogy az adott nyelvosztályba tartozik-e vagy sem.

A dolgozatban rövid ismertetőt adok a formális nyelvek és automaták fejlődéséről. Bemutatom a formális nyelvet, nyelvosztályait, valamint az automaták és nyelvek kapcsolatát. Végül ismertetem a nyelvek zártságát bizonyos műveletekre nézve.