5.6. Véges automaták analízise

Az automaták analízisének problémáját véges automatákra így módosítjuk:

A véges automaták analízise jelentse olyan univerzális algoritmus megadását, amelynek alkalmazásával bármely adott determinisztikus F A=(Q, T, q 0, d, F) véges automatához meg tudjuk adni annak a nyelvnek egy reguláris kifejezését, amely F A- ban az F halmazzal előállítható. Ilyen algoritmus létezését S. C. Kleene bizonyította be 1956-ban. Mi a továbbiakban McNaughton és Yamada algoritmusát ismertetjük, amely egyben konstruktív bizonyítását is szolgáltatja a következő tételnek.

26. Tétel. Ha a véges T halmaz feletti L nyelv előállítható véges kimenő jel nélküli iniciális automata állapotai valamely F részhalmazával, akkor az L nyelv megadható reguláris kifejezéssel.

Bizonyítás. A kívánt algoritmus megadásához nyilván elég olyan eljárást megkonstruálni, amely lehetővé teszi az olyan nyelv egy reguláris kifejezésének felírását, amely F A- ban tetszőleges, egyetlen állapottal előállítható, hisz ha F={q 1, q 2, …, q n }, akkor L F A F =L F A q 1 L F A q 2 ∪⋅⋅⋅∪L F A q n . Így a továbbiakban csupán az olyan reguláris nyelvek reguláris kifejezéssel történő megadását vizsgáljuk, melyek mindegyike F A- ban egy-egy állapottal (azaz az állapotok egy-egy egyelemű részhalmazával) előállítható. Legyen F A=({1, …, n}, T, 1, d, F) egy véges iniciális kimenő jel nélküli automata, melyben az állapothalmaz 1- től alkalmas n- ig terjedő természetes számok halmaza, s az 1 természetes szám a kezdőállapot. Az állapothalmaz és a kezdőállapot ilyen megválasztása nem jelent igazi megszorítást, hisz tetszőleges véges iniciális kimenő jel nélküli automata esetén jelölhetjük 1- el a kezdőállapotot, s amennyiben az állapotok száma n, az {1, 2, …, n}- el az állapothalmazt (aszerint hogy az állapotok egy tetszőleges, kezdőállapottal kezdődő felsorolásánál beszélünk első, …, n- edik állapotról). Jelölje L i, j k tetszőleges i, j∈{1, …, n}- re és k∈{0, 1, …, n}- re azt a nyelvet, mely azokból és csak azokból a bemenő szavakból áll, amelyek hatására az F A az i∈{1, …, n} állapotból átmegy a j∈{1, …, n} állapotba úgy, hogy k=0 esetén nincs közbülső állapot, k>0 esetén pedig legfeljebb az 1, …, k állapotok léphetnek fel közbülső állapotként. Speciálisan, L i, j 0 jelöli azt a nyelvet, amelynek elemei hatására F A az i∈{1, …, n} állapotból közvetlenül, közbülső állapotok nélkül megy át a j∈{1, …, n} állapotba. (Itt tehát k nem kitevőt hanem egyszerűen indexet jelöl!)

Elegendő megmutatni, hogy bármely m∈{1, …, n} esetén az L 1, m n reguláris, hiszen L F A m =L 1, m n , s elegendő ezen nyelvek egy reguláris kifejezését megadni. Ennél valamivel többet bizonyítunk: Igazolni fogjuk, hogy minden L i, j k nyelv reguláris és rekurzív formulát adunk az ilyen nyelvek egy reguláris kifejezésének felírásához. Ez egyben azt is jelenti, hogy tételünknek egy teljes indukciós bizonyítását adjuk.

Legyen k=0. Mivel az L i, j k nyelvek mindegyike vagy az üres nyelv, vagy pedig T bizonyos elemeinek egyesítési halmaza, ezért minden ilyen nyelv reguláris és az automata átmeneti táblázata alapján felírható. Nevezetesen, a táblázat i állapothoz tartozó oszlopában kigyűjtjük azokat az állapotokat, melyek j- vel megegyeznek, s tekintjük az összes olyan a i 1 , …a i s T bemenő jeleket, melyek az F A átmeneti táblázatában ezen j- vel megegyező elemekkel egy sorba esnek. Ezek a bemenő jelek lesznek azok, melyek hatására az F A átmegy az i állapotából a j állapotába. Ha ilyen bemenő jel nincs és ij, akkor L i, j 0=∅ lesz a tekintett reguláris kifejezés. Amennyiben van olyan bemenő jel, mely az i állapotot a j állapotba viszi át és ij, akkor L i, j 0=a i 1 +a i 2 +…+a i s lesz a megfelelő reguláris kifejezés. Ha nincs az i- t a j- be átvivő bemenő jel, de i=j, akkor L i, j 0=λ, hisz az üresszó hatására minden állapot át tud menni önmagába közbülső állapot nélkül, definíció szerint. Végül, ha van olyan bemenő jel, mely az i állapotot a j állapotba viszi át és i=j, akkor nyilvánvalóan igaz, hogy L i, j 0=λ+a i 1 +a i 2 +…+a i s megfelelő reguláris kifejezés.

Legyen most k>0, s tegyük fel, hogy az L i, j 0, …, L i, j k-1, i, j∈{1, …, n} nyelvek regularitását már bebizonyítottuk és fel is írtuk ezen nyelvek egy-egy reguláris kifejezését. Mutassuk meg, hogy érvényes az L i, j k =L i, j k-1+L i, k k-1(L k, k k-1)* L k, j k-1(i, j, k∈{1, …, n}) formula. Az egyenlőség igazolásához először azt gondoljuk végig, hogy milyen módon tudunk egy wT * szóval eljutni az i állapotból a j állapotba úgy, hogy legfeljebb 1, …, k léphetnek fel közbülső állapotként.

Ha valamely wT * szóval az i állapotból a j állapotba el tudunk jutni úgy, hogy legfeljebb az 1, 2, …k léphetnek fel közbülső állapotokként, akkor vagy el tudunk jutni ezen w szóval az i állapotból a j állapotba úgy, hogy legfeljebb 1, …, k-1 léphet fel közbülső állapotként (azaz ha k=1 akkor ezesetben nem lép fel közbülső állapot) és ekkor wL i, j k-1, vagy nem. Utóbbi esetben fel kell lépnie a k állapotnak legalább egyszer, de persze véges sokszor közbülső állapotként. Vagyis ekkor először eljutunk a k állapotba úgy, hogy legfeljebb 1, …, k-1 léphet fel közbülső állapotként, s ha k csak egyszer lépett fel közbülső állapotként, akkor k- ból máris tovább juthatunk j- be úgy, hogy ismét legfeljebb 1, …, k-1 léphet fel közbülső állapotként. Ezesetben tehá w=w 1 w 2, ahol w 1L i, k k-1, w 2L k, j k-1. Az az eset van még hátra, mikor k egynél többször (de persze véges sokszor) lép fel közbülső állapotként. Ekkor is először eljutunk a k állapotba úgy, hogy legfeljebb 1, …, k-1 léphet fel közbülső állapotként, majd véges sokszor k- ból elindulva visszatérünk k- ba úgy, hogy ismét legfeljebb 1, …, k-1 léphessenek fel közbülső állapotként, s végül mint az előző esetben, k- ból tovább juthatunk j- be úgy, hogy ismét legfeljebb 1, …, k-1 léphet fel közbülső állapotként. Ilyenkor w előáll valamely t>2 természetes számra w=w 1 w 2w t-1 w t alakban úgy, hogy w 1L i, k k-1, w 2, …, w t-1L k, k k-1, illetve w t L k, j k-1. Minden lehetséges esetben azt kaptuk, hogy ha w benne van az egyenlőségünk baloldalán szereplő nyelvben, akkor benne van az egyenlőség jobboldalán álló nyelvben. Az egyenlőség fennállásához be kell még látni az is, hogy ha wT * benne van az egyenlőség jobboldalán lévő nyelvben akkor benne van a baloldalán lévőben is. L i, j k-1L i, j k definíció szerint fennáll, így csak azzal az esettel kell foglalkoznunk, mikor wL i, k k-1(L k, k k-1)* L k, j k-1. Ekkor w=w 1⋅⋅⋅w s , s ≥ 1, ahol w 1 az i állapotot a j állapotba, w s a k állapotot a j állapotba, s ha s>2, akkor minden egyes w l , l∈{2, …, s-1} tényező a k állapotból önmagába viszi át az F A automatát úgy, hogy legfeljebb 1, …, k-1 léphetnek fel közbülső állapotként. Világos, hogy ekkor w hatására úgy juthatunk el az i állapotból a j állapotba, hogy legfeljebb 1, …, k léphetnek fel közbülső állapotként. Ezzel a tétel teljes bizonyítást nyert. ∎

Az előző bizonyításban szereplő konstrukció segítségével tetszőleges véges automatához elkészíthetjük a megfelelő reguláris kifejezést.

5.43. példa - Ekvivalens reguláris kifejezés megadása véges automatához 1. feladat

Adjunk meg az A=({a 1 ,a 2},{x,y},a 1 ,δ,{a 2}) determinisztikus véges automatával ekvivalens reguláris kifejezést! Ahol az átmenetfüggvény a következő:

δ a 1 a 2
x a 2 a 2
y a 1


Megoldás:
(I.) Jelöljük n-el az automata állapotainak számát. (Jelen eseben n=2.)
A feladat megoldásához előállítjuk az rij
                  k
               
 reguláris kifejezéseket, a következő rekurzív definíció
segítségével:
rij
               

               0
               ={x|δ(ai,x)=aj
               
}, ha i ≠ j,
r
               
                  ij
               

               0={x|δ(a
               i,x)=a
               j}∪{λ}, ha i=j,
r
               
                  ij
               

               
                  k
               
=r
               
                  ik
               

               
                  k-1
(r
               
                  kk
               

               
                  k-1
)*
               r
               
                  kj
               

               
                  k-1
r
               
                  ij
               

               
                  k-1
, ha 1 ≤ k ≤ n.
 
Jelen esetben r
               
                  ij
               

               
                  k
               
 reguláris kifejezések:

δ k=0 k=1 k=2
r 11 k y∪λ y * y *
r 12 k x y * x y * x x *
r21 k
r 22 k x∪λ x∪λ x *


Például az r
               11
               1=r
               11
               0(r
               11
               0)*
               r
               11
               0∪ r
               11
               0=(y∪ λ)(y∪ λ)*(y∪λ)∪ (y∪ λ)=y
               * és
az r
               12
               2=r
               12
               1(r
               22
               1)*
               r
               22
               1∪ r
               12
               1=y
               *
               x(x∪λ)*(x∪λ)∪ y
               *
               x=y
               *
               x
               x
               *.
                
(II.)

Ezek után L(A)= r m n , ahol r 1 a kezdőállapot, az r m pedig befutja a végállapotok halmazát. Jelen esetben egyetlen végállapotunk van, így L(A)=r 12 2=y * x x *. Megfigyelhető, hogy k=n esetén elegendő azokat az r ij k elemeket kiszámolni, ahol i kezdőállapot és j végállapot. A továbbiakban ezek szerint fogunk eljárni. ★


5.44. példa - Ekvivalens reguláris kifejezés megadása véges automatához 2. feladat


 Adjunk meg az A=({a
               1
               ,a
               2},{x,y,z},a
               1
               ,δ,{a
               1
               ,a
               2}) determinisztikus véges automatával ekvivalens
 reguláris kifejezést, ahol a δ átmenetfüggvény a következő táblázattal adott:

δ a 1 a 2
x a 2
y a 1 a 2
z a 1


Megoldás:

 (I.)

Az r ij k reguláris kifejezések:

δ k=0 k=1
r 11 k y∪λ y *
r 12 k x y * x
r 21 k z zy *
r 22 k y∪λ zy * xy∪λ


 (II.)
 r
               11
               2=r
               12
               1(r
               22
               1)*
               r
               21
               1r
               11
               1=y
               *
               x(zy
               *
               xy∪λ)*
               zy
               *y
               *=
 =y
               *
               x(zy
               *
               xy)*
               zy
               *y
               *,

 r
               12
               2=r
               12
               1(r
               22
               1)*
               r
               22
               1r
               12
               1=y
               *
               x(zy
               *
               xy∪λ)*(zy
               *
               xy∪λ)∪y
               *x=
 =y
               *
               x(zy
               *
               xy)*.
 
 Végül L(A)=r
               11
               2r
               12
               2= (y
               *
               x(zy
               *
               xy)*
               zy
               *y
               *)∪(y
               *
               x(zy
               *
               xy)*)=
 =y
               *
               x(zy
               *
               xy)*(zy
               *∪λ)∪y
               *. ★
 


5.45. példa - Ekvivalens reguláris kifejezés megadása véges automatához 3. feladat


 Adjunk meg az A=({a
               1
               ,a
               2
               ,a
               3},{x,y},a
               1
               ,δ,{a
               2
               ,a
               3}) determinisztikus véges automatával ekvivalens
 reguláris kifejezést, ahol a δ átmenetfüggvény:

δ a 1 a 2 a 3
x a 2 a 3 a 1
y a 3 a 2


Megoldás:

 (I.)

Az r ij k reguláris kifejezések:

δ k=0 k=1 k=2
r 11 k
r 12 k x x xy *
r 13 k y y yxy * x
r 21 k
r 22 k y∪λ y∪λ y *
r 23 k x x y *x
r 31 k x x x
r 32 k xx xxy *
r 33 k λ λ∪xy λ∪xyxxy * x


 (II.)
 
 
 r
               12
               3=(y∪ xy
               *
               x) (λ∪ xyxxy
               *
               x
               *
               xxy
               *∪ xy
               *=
 =(y∪ xy
               *
               x)(xy∪ xxy
               *
               x)*
               xxy
               *∪ xy
               *,
 
 
 r
               13
               3=(y∪ xy
               *
               x)(λ∪ xy∪ xxy
               *
               x)* (λ∪xy∪ xxy
               *
               x)∪ (y∪ xy
               *x)=
 =(y∪ xy
               *
               x)(xy∪ xxy
               *
               x)*,
 
 
 L(A)=r
               12
               3∪ r
               13
               3=((y∪ xy
               *
               x) (xyxxy
               *
               x)*
               xxy
               *∪ xy
               *)∪((y∪ xy
               *
               x)(xyxxy
               *
               x)*)=
 (y∪ xy
               *
               x) (xy∪ xxy
               *
               x)*(xxy
               *∪λ)∪xy
               * ★