A 19. óra vázlata:
Atomataelmélet: A Rabin–Scott-automata
Az eddigieken a formális nyelveket generatív szempontból vizsgáltuk, vagyis a nyelvtan (generatív grammatika) szemszögéből. A generatív grammatika egy olyan eszköz, amely bizonyos szabályok megtartásával előállítja az L nyelvet. Elvileg sorra vehető az összes lehetséges helyettesítés (persze ezek általában végtelenül sokan vannak, de sorravehetők), és listába lehet szedni az összes így legyártott terminális sorozatot: ezek alkotják a generált nyelvet. Az automataelmélet ezzel szemben akceptív megközelítést tükröz: az automata egy olyan eszköz, amely egy terminális sorozatot olvas (megállapodás szerint balról jobbra, bár ennek különösebb jelentősége nincsen), majd valamilyen módon közli, hogy a sorozatot elfogadta-e vagy sem. (Accept/reject válasz.) Az automaták különfélék, és az osztályozás során figyelembe vesszük, hogy képesek-e belső feljegyzéseket készíteni, determinisztikusak-e avagy sem (működésük egy állapottól és egy beolvasott terminális jeltől függ, de ekkor meghatározott — avagy meg van-e engedve a számukra, hogy a leírt helyzeten többféleképpen, véletlenszerűen döntsenek); illetve, hogy belső feljegyzéseik terjedelme korlátozott-e vagy sem. E szempontok szerint különféle automataosztályok alakulnak ki, amelyek párhuzamba lesznek állíthatók a Chomsky-féle nyelvosztályokkal. Egy automata által elfogadott terminálissorozatok összességét az automata nyelvének nevezzük. Az első automataosztály, amelyet vizsgálni fogunk, a Rabin–Scott-automata, amely egy véges belső állapottérrel rendelkező, feljegyzéseket készíteni nem képes automataosztály. Látni fogjuk, hogy a
Rabin–Scott-automaták által elfogadott nyelvek összessége éppen a reguláris nyelvek (Chomsky-féle 3as) osztálya. A determinisztikus Rabin–Scott-automata egy (A, T, f, S, V) algebrai struktúra, amelyben
A véges halmaz: az automata állapottere
T véges halmaz: a terminális jelek ábécéje
f: AT A függvény: az automata átmenetfüggvénye
S A kitüntetett állapot: az automata kezdő(avagy iniciális) állapota
V A halmaz: az automata végállapotainak halmaza
Az automata működése kezdetén az S állapotban van, és a beolvasandó terminálissorozat első pozícióján áll. Egy működési lépés alatt azt értjük, hogy ha az automata valamely B A állapotban van, és a jelsorozatból éppen egy x T jelet olvas, akkor az f(B, x) állapotba kerül, és a jelsorozat következő jelére lép. Amikor a jelsorozat véget ért, meg kell vizsgálni, hogy az automata mely állapotban van. Tételezzük fel, hogy ez a Z A állapot. Ha pedig Z V, akkor azt mondjuk, hogy az automata a jelsorozatot elfogadta, ha Z V, akkor azt mondjuk, hogy az automata a jelsorozatot elutasította. Az elmondottakból következik, de kiemeljük, hogy az automata pontosan akkor fogadja el a -t, ha S V. Lássunk ekkor egy konkrét Rabin–Scott-automatát!
Az automata állapottere az A = {S, B, C, D} halmaz. Terminális ábécéje a T = {x, y, z} halmaz. Iniciális állapota az S állapot. Az ábrán ezt a „semmiből” bejövő nyíl jelzi. Az automata végállapothalmaza a V = {D} halmaz (ennek az automatának egyetlen végállapota van), amit az ábrán a dupla falú kör jelez. Az automata f átmenetfüggvénye a nyilak felirataiból is kiolvasható, de táblázatba foglalva az alábbi: f
x
y
z
S
B
S
S
B
S
C
S
C
S
S
D
D
D
D
D
Szavakkal: az automata az S állapotból az x jel beolvasásának hatására a B állapotba kerül, y vagy z olvasására az S állapotban marad. A többi állapothoz tartozó diagramrészlet (illetve f-táblázat) hasonlóképpen olvasható. Rövid próbálgatás után meggyőződhetünk arról, hogy ez az automata éppen az L = {pxyzq | p, q T* & p rx & p rxy} nyelvet fogadja el. (Olyan pxyzq alakú
mondatokat, amelyekben p nem végződhet sem x-re, sem xy-ra.) Ha az lett volna a feladat, hogy készítsünk reguláris grammatikát ennek az L nyelvnek, akkor (alighanem) az alábbi megoldással rukkoltunk volna elő:
S xB | yS | zS
B xS | yC | zS
C xS | yS | zD
D xD | yD | zD
D
Az automata és a nyelvtan közötti kapcsolatról a következőket mondhatjuk:
Az automata és a nyelvtan terminális ábécéje azonos (T).
Az automata állapotai megfelelnek a nyelvtan nemterminálisainak.
Az automata iniciális állapota (S) a nyelvtan mondatszimbóluma.
Ha az automatában f(X, x) = Y fennáll, akkor a nyelvtanban fellép egy X xY helyettesítési szabály.
Ha az automatában X V, akkor a nyelvtanban fellép egy X helyettesítési szabály.
Azt az eddigiek alapján meg tudjuk állapítani, hogy ezzel az algoritmussal minden Rabin–Scottautomatához készíthető egy reguláris grammatika, azzal a tulajdonsággal, hogy ha az automata elfogad egy p jelsorozatot, akkor az a grammatikában levezethető lesz. Vagyis: Minden determinisztikus Rabin–Scott-automatához található egy vele ekvivalens reguláris nyelvtan.
Jó volna, ha minden reguláris grammatikához úgyszintén található lenne egy vele ekvivalens determinisztikus Rabin–Scott-automata. De mi hiányzik ehhez? Két problémát észlelünk: 1. A reguláris grammatikákban nemcsak az X xY és az X alakú szabályok a megengedettek, hanem az X x alakúak is. 2. Semmi sem zárja ki egy reguláris grammatikában, hogy egy X xY alakú szabály mellett egy X xZ szabály is ott legyen. Márpedig azt mondtuk, hogy a determinisztikus Rabin–Scott-automatában f függvény, amit másképpen úgy is fogalmazhatunk, hogy
alakú részlet nem lehet az automata ábrájában. Az első probléma kiküszöbölésére bevezetünk egy eddig nem használt W nemterminálist, és minden X x alakú szabályt helyettesítünk a következő két szabállyal: X xW és W . A második probléma viszont ilyen kiküszöböléssel nem hárítható el; egy teljesen általános reguláris nyelvtan egy nemdeterminisztikus Rabin–Scott-automatának fog megfelelni.
A nemdeterminisztikus Rabin–Scott-automata egy (A, T, R, S, V) algebrai struktúra, amelyben
A véges halmaz: az automata állapottere
T véges halmaz: a terminális jelek ábécéje
R ATA reláció: az automata átmenetrelációja (!)
S A kitüntetett állapot: az automata kezdő(avagy iniciális) állapota
V A halmaz: az automata végállapotainak halmaza
Az automata működése kezdetén az S állapotban van, és a beolvasandó terminálissorozat első pozícióján áll. Egy működési lépés alatt azt értjük, hogy ha az automata valamely B A állapotban van, és a jelsorozatból éppen egy x T jelet olvas, akkor egy olyan C állapotba kerül, amelyre (B, x, C) R fennáll, és a jelsorozat következő jelére lép. Hogy az ilyen formán megengedett C állapotok közül melyiket választja, azt az automata (véletlenszerűen) dönti el. Azt mondjuk, hogy az automata a p T* mondatot elfogadta, ha az automata működhet úgy, hogy a p elolvasása után végállapotban legyen. Az eddigiekből világos tehát, hogy minden reguláris grammatikának megfeleltethető egy nemdeterminisztikus Rabin–Scott-automata. Szerencsére ez nem veszteség, mert — mint látni fogjuk — minden nemdeterminisztikus Rabin– Scott-automatához konstruálható vele elfogadás szempontjából ekvivalens determinisztikus Rabin–Scott-automata, és ezzel a reguláris nyelvtanok és a determinisztikus Rabin–Scottautomaták ekvivalenciája biztosítva lesz. Innen folytatjuk a következő órán.
