4.7. Automaták analízise és szintézise

Az automaták és az automata leképezések kapcsolatát illetően két ellentétes kérdés fogalmazható meg:

I. Ha adva van egy iniciális automata, meghatározandó az áltata indukált leképezés (analízis);

II. Ha adva van egy iniciális automata leképezés, meghatározandó legalább egy olyan iniciális automata, amely ezt a leképezést indukálja (szintézis).

A szintézis feladata nem egyértelmű ugyan, de egyértelművé tehető a minimalizálás feladatával. Az analízis és szintézis feladata csak akkor fogalmazható meg egzakt módon, ha megállapodunk abban, hogy mit értünk automata és automata leképezés megadásán. Véges automatát például táblázattal adunk meg. Véges automata leképezések megadása általában problémát jelent a végtelen értelmezési tartomány miatt. Bizonyos esetekben viszont közönséges módon is lehetséges. Így például T={a}, V={b, c} mellett a λ → λ, a n b c n-1, n ≥ 1 kifejezésekkel nyilván egy automata leképezést adtunk meg. Az analízis és szintézis probléma ebben a megfogalmazásban túl általános. Ezért ezt a két feladatot csak véges automatákra fogalmazzuk meg pontosabban. Ezzel kapcsolatban egy további probléma is fellép:

0. Meg kell adnunk a véges automaták által indukálható automata leképezéseknek az automatáktól független leírását. Más szóval, keresnünk kell olyan írásmódot, amelyben el tudjuk dönteni, hogy valamely, ebben az írásmódban megadott automata leképezés indukálható-e véges automatával vagy sem. Ezek után véges automatákra az analízis és szintézis problémája így fogalmazható meg:

I'. Bármely adott véges automata esetén meg kell tudnunk adni a szóban forgó írásmódban azt a leképezést, amelyet az automata indukál;

II'. Ha ebben az írásmódban meg van adva egy véges automata által indukálható leképezés, akkor meg kell tudnunk adni legalább egy olyan automatát, mely ezt a leképezést indukálja és állapothalmaza véges.

Egy olyan leképezés megadási módszer, mely eleget tesz a 0.,I.',II.' feltételeknek, először S. C. Kleene talált 1956-ban, bevezetve a reguláris kifejezés fogalmát (lásd: Reguláris kifejezések). Ennek megfelelően az automaták szintézisét és analízisét véges elfogadó automatákra tesszük meg a reguláris nyelvek fejezetben.