5.7. Véges automaták szintézise

Az automaták szintézisének problémáját véges automatákra a következőképp módosítjuk: A véges automaták szintézise jelentse olyan univerzális algoritmus megadását, amelynek alkalmazásával bármely véges T halmaz feletti, reguláris kifejezéssel megadott L reguláris nyelvhez meg tudunk konstruálni olyan véges F A=(Q, T, q 0, d, F) automatát, amelyben az adott L nyelv az állapothalmaz F részhalmazával előállítható, ( vagyis legyen F A az L reguláris kifejezéssel megadott nyelv felismerő automatája). Egy ilyen algoritmus megadása egyben a következő tétel konstruktív bizonyítását szolgáltatja:

27. Tétel. Egy véges T halmaz feletti tetszőleges r reguláris kifejezéshez megadható olyan F A véges felismerő automata amely az r által leírt nyelvet fogadja el.

Bizonyítás. A tétel első bizonyítása ugyancsak S. C. Kleene eredménye 1956-ból. Mi egy V. M. Gluskovtól származó egyszerű eljárást ismertetünk, amely eléggé gazdaságos is abban az értelemben, hogy az esetek többségében a minimálishoz közeli automatát eredményez. Másrészt lehetővé teszi, hogy az adott véges sok, reguláris kifejezéssel megadott reguláris nyelv esetén egyszerre szerkesszünk meg egy olyan véges automatát, amelyben a nyelvek mindegyike előállítható (általában az állapothalmaz más-más részhalmazaival).

A módszer lényege, hogy számba vesszük azoknak a szavaknak a struktúráját, amelyek az adott nyelvek közül legalább egyikben előfordulnak. Az eljárás ismertetése során a könnyebb megértés kedvéért egy példát is kidolgozunk. Legyenek L 1, L 2, …, L k olyan nyelvek a T={a (1), a (2), …, a (n)} ábécé felett (az 1, 2, …, n itt nem kitevőt, hanem indexet jelentenek), amelyek reguláris kifejezésekkel vannak megadva. A módszer alkalmazása előtt a nyelvalgebra alapműveleteire megismert műveleti azonosságok alkalmazásával hozzuk a reguláris kifejezéseket minél rövidebb alakra. Ezt követően indexeljük a reguláris kifejezésekben előforduló betűket balról jobbra haladva úgy, hogy az azonos betűk különböző előfordulási helyükön más-más indexet kapjanak.

5.46. példa - Automata megadása reguláris kifejezéshez

Legyenek az előállítandó nyelvek L 1=a a *, L 2=b b *, L 3=(a a * b+b b * a)(a+b)*.


Ekkor egy lehetséges indexelés eredménye:

L 1=a 1 a 2 *, L 2=b 3 b 4 *, L 3=(a 5 a 6 * b 7+b 8 b 9 * a 10)(a 11+b 12)*.

Legyenek u és v indexelt betűk. Azt mondjuk, hogy az u indexelt betű megelőzi a v indexelt betűt, jelekben: uv, ha az u index nélküli u ' és v index nélküli v ' formájához létezik olyan p szó, mely benne van legalább egy adott L i (1 ≤ i ≤ k) nyelvben és előáll p=w u 'v 'z alakban valamely w, zT *- ra. Az u indexelt betűt kezdőbetűnek nevezzük, ha index nélkül formája első betűje legalább egy olyan szónak, amely legalább egy L i (1 ≤ i ≤ k)- ben benne van. Végül, az u indexelt bezűt záróbetűnek hívunk, ha index nélküli formája utolsó betűje olyan szónak, mely legalább egy L i (1 ≤ i ≤ k)- ben benne van.

Az 5.46. példa - Automata megadása reguláris kifejezéshez megoldásának folytatása: betűk osztályozása

Példánkban a kezdőbetűk: a 1, b 3, a 5, b 8.

Záróbetűk: a 1, a 2, b 3, b 4, b 7, a 10, a 11, b 12.

Emellett:

a 1a 2; b 7a 11, b 12;
a 2a 2; b 8b 9, a 10;
b 3b 4; b 9b 9, a 10;
b 4b 4; a 10a 11, b 12;
a 5a 6, b 7; a 11a 11, b 12;
a 6a 6, b 7; b 12a 11, b 12;

Ezek után a keresett véges felismerő F A=(Q, T, q 0, d, F) automatát a következő módon definiáljuk:

Legyen q 0 tetszőleges szimbólum. Legyen ezután d(q 0, a (i)) minden i=1, …, n- re az a (i) betű azon indexelt változatainak azon q 1 (i) halmaza, melyek kezdőbetűk. Ily módon definiáljuk először a q 1 (1), q 1 (2), …, q 1 (n) halmazokat mint F A- beli állapotokat. Megjegyezzük, hogy ha valamelyik T- beli a (i) betű egyik indexelt változata sem kezdőbetű, akkor q (i) az üres halmaz.

A többi állapotot rekurzióval definiáljuk a következő módon: Ha már egy q állapot definiálva van, akkor minden i=1, …, n- re a d(q, a (i)) állapot legyen az a (i) betű azon indexelt változatainak halmaza, melyeket megelőz legalább egy q- beli betű. (Ez a q- beli indexelt betű természetesen nem szükségképp az a (i) betű indexelt változata.) Természetesen előfordulhat az is, hogy az a (i) betűnek nincs egyetlen ilyen indexelt változata sem, s ekkor d(q, a (i)) az üres halmaz. Az is előfordulhat, hogy q maga is az üres halmaz. Ezesetben d(q, a (i))=q fog fennállni a konstrukciónk értelmében.

Világos, hogy az így definiált F A automata iniciálisan összefüggő, azaz a kezdőállapotából alkalmas bemenő szavakkal bármely állapota elérhető. Az is világos, hogy véges, hisz állapotainak száma legfeljebb annyi mint a bemenő ábécé összes részhalmazainak halmaza, azaz 2 n +1. Végül, konstrukciónk alapján minden pL i , i=1, …, k nem üresszó esetén a p szó az így megkonstruált automatát a kezdőállapotból egy olyan állapotba viszi át, melynek legalább egy indexelt betűje az L i nyelv záróbetűje. Ugyancsak konstrukciónk alapján látható, hogy ha qL i akkor ez nem áll fenn. Tehát minden i=1, …, k- ra az L i ∖{λ} nyelv előállítható az F A automatában azzal az F i halmazzal, amely azokból az állapotokból áll, melyek legalább egy L i - beli záróbetűt tartalmaznak. Amennyiben az üresszó eleme L i - nek, akkor F i - hez még hozzá kell venni a q 0 kezdőállapotot is.

Az 5.46. példa - Automata megadása reguláris kifejezéshez folytatása: a megkonstruált automata:

Példánkban az F A automata megszerkesztése így alakul:

d(q 0, a)={a 1, a 5}=q 1, d(q 4, b)={b 12}=q 8,
d(q 0, b)={b 3, b 8}=q 2, d(q 5, a)={a 11}=q 7,
d(q 1, a)={a 2, a 6}=q 3, d(q 5, b)={b 12}=q 8,
d(q 1, b)={b 7}=q 4, d(q 6, a)={a 11}=q 7,
d(q 2, a)={a 10}=q 5, d(q 6, b)={b 12}=q 8,
d(q 2, b)={b 4, b 9}=q 6, d(q 7, a)={a 11}=q 7,
d(q 3, a)={a 2, a 6}=q 3, d(q 7, b)={b 12}=q 8,
d(q 3, b)={b 7}=q 4, d(q 8, a)={a 11}=q 7,
d(q 4, a)={a 11}=q 7, d(q 4, b)={b 12}=q 8.

A kapott q 0 kezdőállapotú automata átmenet táblázata:

F A q 0 q 1 q 2 q 3 q 4 q 5 q 6 q 7 q 8
a q 1 q 3 q 5 q 3 q 7 q 7 q 5 q 7 q 7
b q 2 q 4 q 6 q 4 q 8 q 8 q 6 q 8 q 8

Ebben az automatában előállítható

az L 1 nyelv az F 1={q 1, q 3} végállapothalmazzal,

az L 2 nyelv az F 2={q 2, q 6} végállapothalmazzal,

az L 3 nyelv az F 3={q 4, q 5, q 7, q 8} végállapothalmazzal. ∎ ★

Ezzel tehát beláttuk, hogy a reguláris kifejezések által leírt nyelvosztály éppen a véges automatákkal felismerhető nyelvek osztálya, vagyis a Chomsky-féle 3. típusú nyelvek osztálya.

Ezek szerint egy reguláris nyelvet megadhatunk reguláris nyelvtannal, véges (determinisztikus vagy nemdeterminisztikus) felismerő automatával vagy reguláris kifejezéssel (illetve szintaxis gráffal a Szintaxis gráf alfejezetben ismertetett módon).