5.4. Véges elfogadó automaták (Rabin-Scott automaták)

E fejezetben megmutatjuk, hogy a 3-as típusú, azaz reguláris nyelvtanokkal generálható nyelvek osztálya megegyezik a véges automaták által felismerhető nyelvek osztályával. Más szóval, a 3-as típusú, azaz reguláris nyelvtan, mint generatív eszköz, azonos értékű a véges automatával, mint felismerő eszközzel.

Legyen F A=(Q, T, q 0, d, F) véges felismerő automata (FA, az angol finite automaton alapján), ahol Q az állapotok véges nemüres halmaza, T a bemenő- (vagy szalag-) ábécé, q 0Q a kezdőállapot, d az állapot átmenet függvény, FQ pedig a végállapotok vagy elfogadóállapotok halmaza.

A d leképezés alakja alapján beszélhetünk

- nemdeterminisztikus üresszó átmenetet is megengedő automatáról: d:Q×(T∪{λ})  → 2 Q ,

- nemdeterminisztikus üresszó átmenet nélküli automatáról: d:Q×T → 2 Q ,

- (parciális) determinisztikus automatáról: d:Q×TQ (parciális függvény),

- teljesen definiált determinisztikus automatáról: d:Q×TQ (teljesen definiált függvény).

Amint azt a 4. fejezetben (Nemdeterminisztikus és determinisztikus automata és Rabin-Scott automata alfejezetekben) már láttuk, a nemdeterminisztikus véges automata olyan A=(Q, T, q 0, d) rendszer, amely hasonlóan működik, mint az iniciális kimenő jel nélküli (determinisztikus) automata, azzal a különbséggel, hogy a d átmeneti függvény a Q×T szorzathalmazt a Q állapothalmaz részhalmazainak halmazába, vagyis a 2 Q hatványhalmazba képezi le: d:Q×T → 2 Q . Minden qQ, aT párra d(q, a)⊆Q az átmeneti lehetőségek halmaza. Feltételezzük viszont, hogy az A egy qQ állapotból az aT jel hatására mindig egy állapotba megy át (kivéve ha d(q, a)=∅, amikor az átmenet nincs értelmezve), az átmenet azonban A által nincs egyértelműen meghatározva. Továbbá, az üresszó hatására is történhet átmenet, ilyenkor a szalag olvasása nélkül is állapotot válthat az automata. Tehát az automata a diszkrét időskála mentén minden pillanatban egy jól meghatározott állapotban van, egy lépés során olvas (vagy λ- átmenet esetén nem olvas) az input szalagról egy betűt, és ennek hatására állapotot vált (vagy nem vált).

5.16. példa - Egy nemdeterminisztikus véges automata

A p q r
a { q, p }{ p }
b { r }{ q, r }{ r }


A fenti táblázattal definiált A nemdeterminisztikus véges automata például az a bemenő jel hatására a p állapotból átmehet q- be, de maradhat a p állapotban is. A q állapotban az A az a bemenő jelet nem képes feldolgozni. ★

Az automata egy futásának nevezzük azt az állapotsorozatot, amin egy adott input elolvasása közben végigmehet.

Üresszó átmenetet is megengedő automata esetén az automatát megadó táblázatban a terminálisok mellett az üresszó is egy külön sorban szerepel, ahol a d(q, λ) átmenetek szerepelnek megfelelő q állapotok esetén. Gráfokkal hasonlóan adhatjuk meg ezeket az automatákat is azzal a különbséggel, hogy az állapotátmeneteket jelző nyilakon a terminálisok mellett a λ is szerepelhet.

A d függvény értelmezését kiterjesztjük, így definiáljuk a d * kiterjesztett átmenetfüggvényt. Ehhez először minden állapothoz megadjuk annak λ- lezártját, vagyis azt az állapothalmazt, amit az adott állapotból bemenőjel nélkül is elérhetünk. Formálisan: l(q j )- t definiáljuk rekurzívan tetszőleges q j állapotra:

l 0(q j )={q j } ;

l i+1(q j )=l i ∪{q k | q k d(q m , λ), valamely q m l i (q j )}, ha i ≥ 0

ekkor a Q végessége miatt lesz olyan i, hogy l i (q j )=l i+k (q j ) minden k természetes számra; ekkor l(q j )=l i (q j ) halmazt a q j állapot λ- lezártjának nevezzük.

A λ- lezárt fogalmát értelmezhetjük nemcsak állapotokra, de állapot halmazokra is: l(Q ')={q k | q k l(q) valamely qQ ' esetén }.

Ekkor a kiterjesztett átmenetfüggvényt a következőképpen definiáljuk: d*:Q×T *  → 2 Q , ahol minden qQ- ra d *(q, λ)=l(q) és minden aT, wT * párra (Természetesen előfordulhat, hogy d(q, w a)=∅.) Vegyük észre, hogy ez a kiterjesztés lényegesen különbözik az automataelméleti vizsgálatoknál korábban alkalmazott kiterjesztéstől, hisz ott képelemként 2(Q +) - beli elemek léptek fel, míg itt csak 2 Q - beliek.

Egy véges automata akkor fogad el egy wT * input szót, ha van olyan futása amely a w elolvasása után végállapotba ér, vagyis d *(q 0, w)∩F≠∅. Egy automata által elfogadott szavak halmaza jelenti az automata által elfogadott nyelvet.

Ez alapján azt is mondhatjuk, hogy az L nyelv előállítható vagy felismerhető az A automatában az FQ állapot halmazzal, jelekben: L(A)=L A F , ha wLd *(q 0, w)∩F≠∅.

5.17. példa - A páratlan a-ból és páros b-ből álló szavak nyelve

Az alábbi ábrán olyan automatát láthatunk, mely azokat a szavakat fogadja el, melyek páratlan számú a- t és páros számú b- t tartalmaznak.

Az automata működés közben:


5.18. példa - Az x-re végződő szavak nyelve

Az alábbi ábrákon látható egy nemdeterminisztikus automata működése, mely az x- re végződő szavakat fogadja el.


Most lássunk néhány példát nemdeterminisztikus automata működésére.

Az automata nemdeterminisztikus működéssel olyan állapotba jut és olyan szimbólumot olvas, melyekre az állapotfüggvény üres:

Az automata nemdeterminisztikus működés során végigolvassa az inputot, de a működést nem elfogadó végállapotban fejezi be:

Az automata működése során végigolvassa az inputot és végállapottal elfogadja azt:

5.4.1. Véges determinisztikus és nemdeterminisztikus automaták ekvivalenciája

Két automatát ekvivalensnek hívunk, ha az általuk elfogadott nyelvek megegyeznek. Habár az imént bemutatott négy automatafogalom elég különbözőnek tűnhet most megmutatjuk, hogy az általuk elfogadott nyelvek osztálya megegyezik. Egyrészt világos, hogy a bemutatott sorrendben egyre speciálisabbak az automaták, vagyis definíció szerint a nemdeterminisztikus üresszó átmenet nélküli automaták, tulajdonképpen a nemdeterminisztikus üresszó átmenetet is megengedő automaták speciális esetei, amikben üresszó átmenet nem fordul elő. Továbbá a (parciális) determinisztikus automaták a nemdeterminisztikus üresszó átmenet nélküli automaták olyan speciális esetei ahol a d függvény képhalmaza maximum egyelemű halmazokat tartalmaz. A teljesen definiált determinisztikus automaták viszont olyan speciális parciális determinisztikus automaták, amelyekben a d értéke mindig pontosan egyelemű halmaz.

Ezek alapján világos, hogy a teljesen definiált determinisztikus automaták által elfogadott nyelvek osztálya részhalmaza a parciális determinisztikus automaták által elfogadott nyelvek halmazának, amely részhalmaza a nemdeterminisztikus üresszó átmenet nélküli automatákkal elfogadott nyelvek osztályának, az viszont részhalmaza a nemdeterminisztikus üresszó átmenetet is megengedő automaták által elfogadott nyelvek halmazának. Azt, hogy itt nem valódi részhalmaz relációkról van szó a következő tétel, illetve annak bizonyításában szereplő konstrukcióval látjuk be.

22. Tétel. Minden nemdeterminisztikus üresszó átmenetet is megengedő véges automatához van vele ekvivalens teljesen definiált determinisztikus automata.

Bizonyítás. Legyen N F A=(Q, T, q 0, d, F) egy nemdeterminisztikus üresszó átmenetet is megengedő véges automata. Konstruáljuk meg a D F A=(2 Q , T, l(q 0), d ', F ') véges automatát, ahol az állapotok 2 Q halmaza az eredeti automata állapotainak a lehetséges részhalmazaiból áll. A d ' állapotátmenet-függvény definíciója pedig ahol p∈2 Q , vagyis pQ és aT. Az új automata végállapotai pedig F '={p | van olyan qp, hogy qF}. Világos, hogy DFA teljesen definiált determinisztikus véges automata.

Másrészt belátható, hogy L(D F A)=L(N F A), hiszen az eredeti NFA automata minden elfogadó futásához tartozik az új DFA automatának egy elfogadó futása, és viszont. ∎

Az előző tételben megkonstruált DFA tartalmazhat olyan állapotokat, amelyek a kezdőállapotból nem érhetőek el. Például csak olyan p∈2 Q állapotok érhetőek el melyekre p=l(p) teljesül.

Ez alapján, egy determinisztikus automata megkonstruálásakor akkor járunk el észszerűen, ha az l(q 0)- nak megfelelő állapotból indulunk el, és csak azokat az állapotokat (vagyis Q azon részhalmazait) vesszük fel az állapotok közé, amely előáll valamilyen eddigi állapotból valamely bemenőjel hatására.

5.19. példa - Automata determinizálása 1. feladat


Adjunk meg az A=({ a
                  0
                  , a
                  1
                  , a
                  2
                   }, { x, y }, a
                  0
                  , δ, { a
                  1
                   }) nemdeterminisztikus, parciálisan definiált,
kimenő jel nélküli, iniciális, végállapotokkal bővített véges automatával ekvivalens Ad
                  

determinisztikus, teljesen definiált automatát!


δ a 0 a 1 a 2
x { a 2 }{ a 0 }{ a 1 , a 2 }
y { a 1 }{ a 2 }-

Megoldás

  1.  Első lépésben meg kell határozni az új Ad
                         
     automata belső állapotainak halmazát.
    Az A automata kezdőállapotához, valamint azon állapothalmazaihoz,
    melyek elérhetőek a kezdőállapotból, rendeljünk új betűket!
    Ezek az új betűk alkotják az új állapothalmazt.
    Jelen esetben:
    Az A automata kezdőállapotához és a kezdőállapotból egy lépésben elérhető
    állapothalmazokhoz rendeljünk új betűket:
    Jelöljük bi
                         
    -vel ezeket az elemeket!

    b
                         0
                         ={ a
                         0
                          }, b
                         1
                         ={ a
                         2}, b
                         2
                         ={ a
                         1
                          }.
     
    Vegyük fel azokat az állapothalmazokat is, melyek egy lépésben elérhetőek
    a már meglévő állapothalmazokból és még nem szerepeltek:

    b
                         3
                         ={ a
                         1
                         , a
                         2
                          }, b
                         4 = ∅.
     
    Mindezt addig kell folytatni, amíg van újabb elérhető állapothalmaz.
    Amennyiben több állapot is szerepel egy állapothalmazban, - mint az megfigyelhető a b
                         3
    állapothalmaz esetén, - akkor az ezen állapotokból elérhető állapothalmazok unióját kell venni:

    b
                         5
                         ={ a
                         0
                         , a
                         1
                         , a
                         2
                          }.
     
    Mivel újabb bővítés nem lehetséges, készen vagyunk az első lépéssel.
     
     

  2. Második lépésben meghatározzuk az Ad
                         
     automata δ' átmenetfüggvényét.
     Ehhez a következő lépésekre van szükség:

    1. Ha az automata bi
                                 
       = ∅ állapotban van, akkor bármely
      bemenő jel hatására ugyanebben az állapotban marad.

    2. Ha az automata egy bi
                                 
       ≠ ∅ állapotban van, akkor meg kell
      vizsgálni, hogy a bi
                                 
       halmazban lévő a
                                 
                                    l
                                    1
                                 
      , ..., aln
                                    

                                 

      állapotok az adott bemenő jel hatására mely a
                                 
                                    k
                                    1
                                 
      , ... ,akm
                                    

                                 
       állapotokba mennek át.
      Az Ad
                                 
       automata a bi
                                 
       állapotból az adott bemenő jel hatására az
       a
                                 
                                    k
                                    1
                                 
      , ... ,akm
                                    

                                 
       halmazhoz tartozó bj
                                 
       állapotba megy át.

    δ' b 0 b 1 b 2 b 3 b 4 b 5
    x b 1 b 3 b 0 b 5 b 4 b 5
    y b 2 b 4 b 1 b 1 b 4 b 3

  3.  Harmadik lépésben meg kell határozni az Ad
                         
     automata
    bemenő jeleinek halmazát, kezdőállapotát, valamint végállapotainak halmazát.

    • Az Ad automata bemenő jeleinek halmaza megegyezik az A automata bemenő jeleinek a halmazával.

    • Az Ad automata kezdőállapota az A automata kezdőállapotához rendelt bi lesz.

    • Az Ad
                                 
       automata végállapotainak a halmaza pedig tartalmazni fog minden olyan
      bj
                                 
       állapotot, melynek mint halmaznak eleme az A automata bármely végállapota.

    Jelen esetben:
    Ad=({ b
                         0
                         , b
                         1
                         , b
                         2
                         , b
                         3
                         , b
                         4
                         , b
                         5
                          }, { x, y }, b
                         0
                         , δ', { b
                         1
                         , b
                         2
                         , b
                         3
                         , b
                         5
                          }).

5.20. példa - Automata determinizálása 2. feladat

Adjunk meg az A=({ a
                  0
                  , a
                  1
                   }, { x, y }, a
                  0
                  , δ, { a
                  1
                   })
nemdeterminisztikus, parciálisan definiált, kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens Ad
                  
 determinisztikus, teljesen definiált automatát!


δ a 0 a 1
x { a 1 }{ a 0, a 1 }
y { a 0 }-

Megoldás:

  1. b 0={ a 0 }, b 1={ a 1 }, b 2={ a 0, a 1 }, b 3 = ∅.

  2. δ' b 0 b 1 b 2 b 3
    x b 1 b 2 b 2 b 3
    y b 0 b 3 b 0 b 3

  3. Ad=({ b 0 , b 1 , b 2 , b 3 }, { x, y }, b 0 , δ', { b 1 , b 2 }).

5.21. példa - Automata determinizálása 3. feladat

Adjunk meg az A=({ a
                  0
                  , a
                  1
                   }, { x, y, z }, a
                  0
                  , δ, { a
                  0
                   })
nemdeterminisztikus, parciálisan definiált, kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens Ad
                  
 determinisztikus, teljesen definiált automatát!


δ a 0 a 1
x { a 1 }-
y -{ a 0, a 1 }
z { a 0, a 1 }{ a 0 }

Megoldás:

  1. b 0={ a 0}, b 1={ a 1 }, b 2 = ∅, b 3={ a 0, a 1 }.

  2. δ' b 0 b 1 b 2 b 3
    x b 1 b 2 b 2 b 1
    y b 2 b 3 b 2 b 3
    z b 3 b 0 b 2 b 3

  3. Ad=({ b 0 , b 1 , b 2 , b 3 }, { x, y, z }, b 0 , δ', { b 0 , b 3 }).

5.22. példa - Automata determinizálása 4. feladat

Adjunk meg az A=({ a
                  0
                  , a
                  1
                   }, { x, y }, a
                  0
                  , δ, { a
                  1
                   })
nemdeterminisztikus, parciálisan definiált, kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens Ad
                  
 determinisztikus, teljesen definiált automatát!


δ a 0 a 1
x { a 0, a 1 }{ a 0, a 1 }
y { a 0, a 1 }-

Megoldás:

  1. b 0={ a 0 }, b 1={ a 0, a 1 }.

  2. δ' b 0 b 1
    x b 0 b 1
    y b 1 b 1

  3. Ad=({ b 0 , b 1 }, { x, y }, b 0 , δ', { b 1 }).

5.23. példa - Automata determinizálása 5. feladat

Adjunk meg az A=({ a
                  0
                  , a
                  1
                  , a
                  2
                   }, { x, y }, a
                  0
                  , δ, { a
                  0
                  , a
                  1
                   })
nemdeterminisztikus, parciálisan definiált, kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens Ad
                  
 determinisztikus, teljesen definiált automatát!


δ a 0 a 1 a 2
x { a 2 }{ a 1 }{ a 1, a 2 }
y { a 0 }{ a 2 }{ a 0 }

Megoldás:

  1. b 0={ a 0 }, b 1={ a 2 }, b 2={ a 1, a 2 }, b 3={ a 0, a 2 }.

  2. δ' b 0 b 1 b 2 b 3
    x b 1 b 2 b 2 b 2
    y b 0 b 0 b 3 b 0

  3. Ad=({ b 0 , b 1 , b 2 , b 3 }, { x, y }, b 0 , δ', { b 0 , b 2 , b 3 }).

5.24. példa - Automata determinizálása 6. feladat

Adjunk meg az A=({ a
                  0
                  , a
                  1
                  , a
                  2
                   }, { x, y }, a
                  0
                  , δ, { a
                  1
                   })
nemdeterminisztikus, parciálisan definiált, kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens Ad
                  
 determinisztikus, teljesen definiált automatát!


δ a 0 a 1 a 2
x { a 1 }{ a 1, a 2 }{ a 2 }
y --{a 1}

Megoldás:

  1. b 0={ a 0 }, b 1={ a 1 }, b 2 = ∅, b 3={ a 1, a 2 }.

  2. δ' b 0 b 1 b 2 b 3
    x b 1 b 3 b 2 b 3
    y b 2 b 2 b 2 b 1

  3. Ad=({ b 0 , b 1 , b 2 , b 3 },{ x, y }, b 0 , δ', { b 1 , b 3 }).

5.25. példa - Automata determinizálása 7. feladat

Adjunk meg az A=({ a
                  0
                  , a
                  1
                  , a
                  2
                   }, { x, y, z }, a
                  0
                  , δ, { a
                  1
                  , a
                  2
                   })
nemdeterminisztikus, parciálisan definiált, kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens Ad
                  
 determinisztikus, teljesen definiált automatát!


δ a 0 a 1 a 2
x { a 0 }-{ a 0, a 2 }
y { a 1, a 2 }{ a 0 }-
z -{ a 0, a 1 }-

Megoldás:

  1. b 0={ a 0 }, b 1={ a 1, a 2 }, b 2 = ∅, b 3={ a 0, a 2 }, b 4={ a 0, a 1 }, b 5={ a 0, a 1, a 2 }.

  2. δ' b 0 b 1 b 2 b 3 b 4 b 5
    x b 0 b 3 b 2 b 3 b 0 b 3
    y b 1 b 0 b 2 b 1 b 5 b 5
    z b 2 b 4 b 2 b 2 b 4 b 4

  3. Ad=({ b 0 , b 1 , b 2 , b 3 , b 4 , b 5 },{ x, y ,z }, b 0 , δ', { b 1 , b 3 , b 4 , b 5 }).

5.26. példa - Automata determinizálása 8. feladat

Adjunk meg az A=({ a
                  0
                  , a
                  1
                  , a
                  2
                  , a
                  3
                   }, { x, y, z }, a
                  0
                  , δ, { a
                  1
                  , a
                  3
                   })
nemdeterminisztikus, parciálisan definiált, kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens Ad
                  
 determinisztikus, teljesen definiált automatát!


δ a 0 a 1 a 2 a 3
x { a 0 }-{ a 2, a 3 }{ a 1, a 2 }
y { a 1, a 2, a 3 }{ a 0 }-{ a 0 }
z -{ a 1, a 2 }{ a 1, a 3 }{ a 1 }

Megoldás:

  1. b 0={ a 0 }, b 1={ a 1, a 2 , a 3}, b 2 = ∅.

  2. δ' b 0 b 1 b 2
    x b 0 b 1 b 2
    y b 1 b 0 b 2
    z b 2 b 1 b 2

  3. Ad=({ b 0 , b 1 , b 2 },{ x, y ,z }, b 0 , δ', { b 1 }).

5.4.2. Véges determinisztikus elfogadó automaták minimalizálása

Itt mutatjuk be az Aufenkamp-Hohn-féle Minimalizációs Algoritmus determinisztikus elfogadó automatákra működő változatát.

Legyen adott D F A=(Q, T, q 0, d, F). A valódi minimalizásiós algoritmus végrehajtása előtt az iniciális összefüggőséget kell ellenőriznünk, illetve a kezdőállapotból nem elérhető állapotokat törölni: azaz a Q '={d *(q 0, w)|wT *} állapothalmazzal és F '=F∩{d *(q 0, w)|wT *} végállapothalmazzal rendelkező D F A '=(Q ', T, q 0, d ', F ') iniciálisan összefüggő (kimenő jel nélküli) állapot-részautomatát minimalizáljuk.

A továbbiakban legyen D F A=(Q, T, q 0, d, F) iniciálisan összefüggő. A C D F A osztályozást osztályozások egy C 1, C 2, … sorozatán keresztül szerkesztjük meg, melyeket a következőképp definiálunk:

Kezdetként a C 1 osztályozással bontsuk a Q állapothalmazt két részre: F és QF.

Ezután, ha i ≥ 1, úgy a C i+1 osztályozás szerint p és q akkor és csak akkor esnek egy osztályba, ha egyrészt már C i szerint is egy osztályba esnek, másrészt pedig minden bemenő jel hatására egy és ugyanazon C i szerinti osztályba mennek át.

Képletben: ha i ≥ 1, akkor C i+1[p]=C i+1[q]⇔C i [p]=C i [q] és ∀aT:C i [d(p, a)]=C i [d(q, a)].

A Q végessége miatt lesz olyan m, hogy C m osztályozás megegyezik C i+m osztályozással (vagyis megkaptuk a C D F A osztályozást), ekkor a teljesen definiált determinisztikus minimális automatát a következőképpen adjuk meg:

AC m =(C m , T, C m [q 0], d C m , F C m ), ahol minden C m [q]∈C m , aT- re d C m (C m [q], a)=C m [d(q, a)], illetve F C m ={C m [q] | qF}.

Az így kapott automata ekvivalens az eredetivel, ugyanazt az L nyelvet fogadja el; teljesen definiált determinisztikus és minimális állapotszámú.

Ha egy D F A=(Q, T, q 0, d, F) minimális automata esetén vannak olyan T *- beli szavak amelyek nem prefixei (kezdőszeletei) egyetlen L=L(D F A) nyelvbeli szónak sem, azaz van olyan uT *, hogy nincs olyan vT *, hogy u vL, akkor a minimális determinisztikus teljesen definiált automatának van nyelőállapota, vagyis olyan q állapot, amire bármilyen aT bemenőjelre d(q, a)=q és qF.

Például ez a nyelő állapot felel meg egy nemdeterminisztikus automata nem definiált átmeneteinek, vagyis a determinizáló algoritmusban az ∅⊂Q halmaznak.

Természetesen parciális véges automata esetén ez a nyelő állapot elhagyható, így ekkor az állapotszám eggyel csökkenthető.

Amint később látni fogjuk a minimális determinisztikus automata létezésének fontos elméleti jelentősége is van.

5.27. példa - Véges elfogadó automata minimalizálása 1. feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus
segítségével az
A=({a
                  0
                  ,a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5
                  ,a
                  6},{x,y},a
                  0δ
                  ,{a
                  2
                  ,a
                  4
                  ,a
                  5
                  ,a
                  6})
kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens A
                  0 minimális állapotszámú automatát!


δ a 0 a 1 a 2 a 3 a 4 a 5 a 6
x a 2 a 5 a 1 a 1 a 2 a 1 a 0
y a 1 a 0 a 3 a 4 a 5 a 3 a 2


Megoldás:

(O.) Mielőtt az érdemi munkához hozzáfognánk, meg kell vizsgálni, hogy
mely állapotok érhetőek el az A automata kezdőállapotából.
Azokat az állapotokat, melyek nem érhetőek el, egyszerűen töröljük, mivel
nem fognak előfordulni semelyik számítás során sem.

Jelen esetben az a
               0 állapotból elérhető állapotok:
{a
               0,a
               2,a
               1,a
               3,a
               5,a
               4}.
Látható, hogy semmilyen input szó esetén sem kerülhet az A
automata a
               6 állapotba, ezért ezt az állapotot töröljük. Az így kapott
A ' automatát kell a továbbiakban minimalizálnunk az
Aufenkamp-Hohn-féle minimalizációs algoritmus segítségével:
A '=({a
               0,a
               1,a
               2,a
               3,a
               4,a
               5},{x,y},a
               0δ',{a
               2,a
               4,a
               5}).

δ' a 0 a 1 a 2 a 3 a 4 a 5
x a 2 a 5 a 1 a 1 a 2 a 1
y a 1 a 0 a 3 a 4 a 5 a 3


(I.) A feladat megoldásának első lépéseként különböző osztályokba fogjuk
sorolni az A ' automata belső állapotait. A kezdeti osztályozáskor
mindig két osztályba kerülnek az állapotok, attól függően, hogy végállapotok,
vagy pedig nem végállapotok.

Jelen esetben:
C
               1
               ={a
               0
               ,a
               1
               ,a
               3},{a
               2
               ,a
               4
               ,a
               5}.
Ezek után a C
               
                  i+1
-edik osztályozás esetén két állapot akkor esik egy
osztályba, ha egyrészt a Ci
               
-edik osztályozás esetén is azonos
osztályba tartoztak, másrészt pedig minden bemenő jel hatására azonos
Ci
               
-beli osztályban található állapotokba mennek át. Az osztályozás
véget ér, amennyiben Ci
               
=C
               
                  i+1
 valamely i ≥ 1 esetén.

Jelen esetben:
C
               2
               ={a
               0
               ,a
               1},{a
               3},{a
               2
               ,a
               5},{a
               4}.
C
               3
               ={a
               0
               ,a
               1},{a
               3},{a
               2
               ,a
               5},{a
               4}.
Mivel C
               2
               =C
               3, ezért az osztályozás véget ért. A C
               2 osztályait
jelöljük valamely új betűvel, például b-vel:
b
               0
               ={a
               0
               ,a
               1},b
               1
               ={a
               3},b
               2
               ={a
               2
               ,a
               5},b
               3
               ={a
               4}.
(II.) Készítsük el az A ' automatával ekvivalens, minimális állapotszámú
A
               0 automatát, mely állapothalmazát az osztályozás és az új jelölés
bevezetése után kapott bi
               
 betűk alkotják, a bemenő jeleinek halmaza megegyezik
az A automata bemenő jeleinek halmazával, az átmenetfüggvényét megkapjuk
úgy, hogy megnézzük, hogy az adott bi
               
 osztálybeli állapotok
az adott bemenő jel hatására mely bj
               
 osztálybeli állapotokba mentek át az A '
automata esetén, az új kezdőállapot az a bi
               
 lesz, melynek eleme a
               0, és
végül az A
               0 automata végállapotait azon b
               
                  k
                  1
               
,...,bkm
                  

               

osztályok alkotják, mely osztályok elemei az
A ' automata végállapotaiból állnak.

Jelen esetben:
A
               0
               =({b
               0
               ,b
               1
               ,b
               2
               ,b
               3},{x,y},b
               0
               , δ
               0
               ,{b
               2
               ,b
               3}).
 

δ0 b 0 b 1 b 2 b 3
x b 2 b 0 b 0 b 2
y b 0 b 3 b 1 b 2

5.28. példa - Véges elfogadó automata minimalizálása 2. feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus
segítségével az
A=({a
                  0
                  ,a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5
                  ,a
                  6},{x,y},a
                  0δ
                  ,{a
                  0
                  ,a
                  1
                  ,a
                  2
                  ,a
                  3})
kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens A
                  0 minimális állapotszámú automatát!


δ a 0 a 1 a 2 a 3 a 4 a 5 a 6
x a 6 a 6 a 6 a 6 a 5 a 0 a 2
y a 6 a 3 a 0 a 3 a 1 a 4 a 1


Megoldás:

(O.) Az a
               0 kezdőállapotból elérhető belső állapotok:
{a
               0
               ,a
               6
               ,a
               2
               ,a
               1
               ,a
               3}.

A'=({a
               0
               ,a
               1
               ,a
               2
               ,a
               3
               ,a
               6},{x,y},a
               0δ'
               ,{a
               0
               ,a
               1
               ,a
               2
               ,a
               3}).

δ' a 0 a 1 a 2 a 3 a 6
x a 6 a 6 a 6 a 6 a 2
y a 6 a 3 a 0 a 3 a 1


(I.)
C
               1
               ={a
               0
               ,a
               1
               ,a
               2
               ,a
               3},{a
               6}.
C
               2
               ={a
               0},{a
               1
               ,a
               2
               ,a
               3},{a
               6}.
C
               3
               ={a
               0},{a
               1
               ,a
               3},{a
               2},{a
               6}.
C
               4
               ={a
               0},{a
               1
               ,a
               3},{a
               2},{a
               6}.
b
               0
               ={a
               0},b
               1
               ={a
               1
               ,a
               3},b
               2
               ={a
               2},b
               3
               ={a
               6}.

(II.)
A
               0
               =({b
               0
               ,b
               1
               ,b
               2
               ,b
               3},{x,y},b
               0
               , δ
               0
               ,{b
               0
               ,b
               1
               ,b
               2}).

δ0 b 0 b 1 b 2 b 3
x b 3 b 3 b 3 b 2
y b 3 b 1 b 0 b 1

5.29. példa - Véges elfogadó automata minimalizálása 3. feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus
segítségével az
A=({a
                  0
                  ,a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5
                  ,a
                  6
                  ,a
                  7
                  ,a
                  8},{x,y},a
                  0δ
                  ,{a
                  2
                  ,a
                  7})
kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens A
                  0 minimális állapotszámú automatát!
 


δ a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8
x a 3 a 5 a 7 a 0 a 2 a 0 a 4 a 2 a 5
y a 8 a 1 a 3 a 2 a 6 a 7 a 3 a 5 a 2


Megoldás:

(O.) Az a
               0 kezdőállapotból elérhető belső állapotok:
{a
               0
               ,a
               3
               ,a
               8
               ,a
               2
               ,a
               5
               ,a
               7}.

A'=({a
               0
               ,a
               2
               ,a
               3
               ,a
               5
               ,a
               7
               ,a
               8},{x,y},a
               0δ'
               ,{a
               2
               ,a
               7
               ,a
               8}).

δ' a 0 a 2 a 3 a 5 a 7 a 8
x a 3 a 7 a 0 a 0 a 2 a 5
y a 8 a 3 a 2 a 7 a 5 a 2


(I.)
C
               1
               ={a
               0
               ,a
               3
               ,a
               5
               ,a
               8},{a
               2
               ,a
               7}.
C
               2
               ={a
               0},{a
               3
               ,a
               5
               ,a
               8},{a
               2
               ,a
               7}.
C
               3
               ={a
               0},{a
               3
               ,a
               5},{a
               8},{a
               2
               ,a
               7}.
C
               4
               ={a
               0},{a
               3
               ,a
               5},{a
               8},{a
               2
               ,a
               7}.
b
               0
               ={a
               0},b
               1
               ={a
               3
               ,a
               5},b
               2
               ={a
               8},b
               3
               ={a
               2
               ,a
               7}.                                   
(II.)
A
               0
               =({b
               0
               ,b
               1
               ,b
               2
               ,b
               3},{x,y},b
               0
               , δ
               0
               ,{b
               3}).

δ0 b 0 b 1 b 2 b 3
x b 1 b 0 b 1 b 3
y b 2 b 3 b 3 b 1

5.30. példa - Véges elfogadó automata minimalizálása 4. feladat


Készítsük el az Aufenkamp-Hohn-féle minimalizációs algoritmus
segítségével az
A=({a
                  0
                  ,a
                  1
                  ,a
                  2
                  ,a
                  3
                  ,a
                  4
                  ,a
                  5
                  ,a
                  6
                  ,a
                  7},{x,y,z},a
                  0δ
                  ,{a
                  2
                  ,a
                  4
                  ,a
                  5
                  ,a
                  7})
kimenő jel nélküli, iniciális, végállapotokkal bővített
véges automatával ekvivalens A
                  0 minimális állapotszámú automatát!
 


δ a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7
x a 6 a 3 a 1 a 7 a 1 a 0 a 4 a 1
y a 4 a 7 a 0 a 2 a 3 a 1 a 5 a 6
z a 5 a 2 a 6 a 1 a 3 a 6 a 0 a 6


Megoldás:

(O.) Az a
               0 kezdőállapotból elérhető belső állapotok:
{a
               0
               ,a
               6
               ,a
               4
               ,a
               5
               ,a
               1
               ,a
               3
               ,a
               7
               ,a
               2}.
Mivel a kezdőállapotból minden állapot elérhető, ezért nem törlünk
egyetlen állapotot sem, tehát A'=A.
(I.)
C
               1
               ={a
               0
               ,a
               1
               ,a
               3
               ,a
               6},{a
               2
               ,a
               4
               ,a
               5
               ,a
               7}.
C
               2
               ={a
               0
               ,a
               1},{a
               3
               ,a
               6},{a
               2
               ,a
               4
               ,a
               5
               ,a
               7}.
C
               3
               ={a
               0
               ,a
               1},{a
               3
               ,a
               6},{a
               2
               ,a
               5},{a
               4
               ,a
               7}.
C
               4
               ={a
               0
               ,a
               1},{a
               3
               ,a
               6},{a
               2
               ,a
               5},{a
               4
               ,a
               7}.
b
               0
               ={a
               0
               ,a
               1},b
               1
               ={a
               3
               ,a
               6},b
               2
               ={a
               2
               ,a
               5},b
               3
               ={a
               4
               ,a
               7}.
(II.)
A
               0
               =({b
               0
               ,b
               1
               ,b
               2
               ,b
               3},{x,y,z},b
               0
               , δ
               0
               ,{b
               2
               ,b
               3}).

δ0 b 0 b 1 b 2 b 3
x b 1 b 3 b 0 b 0
y b 3 b 2 b 0 b 1
z b 2 b 0 b 1 b 1

5.4.3. Véges automaták és reguláris nyelvtanok ekvivalenciája

23. Tétel. A 3- as típusú nyelvek osztálya egybeesik a véges automatákkal felismerhető nyelvek osztályával.

Bizonyítás. Legyen adott G=(N, T, S, H) reguláris nyelvtan gyenge normálformában. Ekkor megadunk egy nemdeterminisztikus üresszó átmenetet is megengedő N F A=(Q, T, q 0, d, F) automatát, amely L(G) nyelvet fogadja el. Legyen Q=N∪{q f }, ahol q f N. Legyen q 0=S, F={q f }, továbbá a d állapotátmenet-függvényt adjuk meg a követekezőképpen:

minden Aa BH szabály ( A, BN, aT∪{λ}) esetén legyen Bd(A, a) és

minden AaH szabály ( AN, aT∪{λ}) esetén legyen q f d(A, a).

A konstrukció alapján látható, hogy G minden termináló levezetéséhez pontosan egy elfogadó futása lesz az N F A automatának és fordítva.

Most nézzük a fordított konstrukciót: az egyszerűség kedvéért nemdeterminisztikus üresszó átmenet nélküli automatából kiindulva.

Legyen, tehát, adott N F A=(Q, T, q 0, d, F) úgy, hogy QT=∅, definiáljuk a G=(N, T, S, H) nyelvtant a következőképpen: legyen N=Q, S=q 0. A szabályok pedig:

minden pd(q, a) esetén ( p, qQ, aT) legyen qa pH.

továbbá, minden qF esetén legyen qλH.

Könnyen ellenőrizhető, hogy N F A minden elfogadó futásához lesz a G nyelvtanban termináló levezetés, és fordítva. ∎

Képletesen szólva, az előző konstrukciók esetén a következő átalakításokat végezhetjük el:

Ebben a fejezetben tehát beláttuk, hogy a pontosan a reguláris nyelveket fogadják el a véges automaták, akár nemdeterminisztikus üresszó átmenetet is megengedő automatáról, nemdeterminisztikus üresszó átmenet nélküli automatáról, (parciális) determinisztikus automatáról, teljesen definiált determinisztikus automatáról, vagy akár minimális determinisztikus automatákról van szó.

5.31. példa - Ekvivalens reguláris nyelvtan megadása véges automatához 1. feladat


Feladat: Adjunk meg az A=({q
                  0
                  ,q
                  1
                  ,q
                  2},{a,b},q
                  0
                  ,δ,{q
                  0
                  ,q
                  2})
 
 δ(q
                  0
                  ,a)={q
                  1
                  ,q
                  2}, δ(q
                  0
                  ,b)={q
                  2},
 δ(q
                  1
                  ,a)={q
                  0}, δ(q
                  2
                  ,b)={q
                  1}
 
 véges automatával ekvivalens G reguláris nyelvtant!
 


 Megoldás:
 
G nyelvtan nemterminálisainak halmaza az automata állapothalmazával egyezik meg, a terminálisok
halmazát az automata bemenő jeleinek halmaza alkotja, a startszimbólum az automata kezdőállapota
lesz.

G nyelvtan szabályainak halmazát két csoportba oszthatjuk.
 Az első csoportba tartoznak azok a szabályok, melyeket az átmenetfüggvényből kaphatunk meg.
Ha az A automata a qi
                  
 állapotból az x bemenőjel hatására a qj
                  
 állapotba megy át,
akkor a szabályok közé bekerül a qi
                  
 → xqj
                  
 szabály.
 A második csoportba azok a szabályok tartoznak, melyeket a végállapotok alapján adhatunk meg.
Amennyiben a qk
                  
 állapot szerepel az A automata végállapotainak a halmazában,
úgy fel kell vennünk G nyelvtan szabályai közé a qk
                  
 → λ szabályt.
 
Jelen esetben:
G=({q
                  0
                  ,q
                  1
                  ,q
                  2},{a,b},q
                  0
                  ,H),
H={ q
                  0 → aq
                  1
                  , q
                  0 → aq
                  2
                  , q
                  0 → bq
                  2
                  , q
                  1 → aq
                  0
                  , q
                  2 → bq
                  1
                  , q
                  0 → λ, q
                  2 → λ }. ★
 


5.32. példa - Ekvivalens reguláris nyelvtan megadása véges automatához 2. feladat


Adjunk meg az A=({q
                  0
                  ,q
                  1},{x,y},q
                  0
                  ,δ,{q
                  1}),

δ(q
                  0
                  ,x)={q
                  0
                  ,q
                  1}, δ(q
                  1
                  ,y)={q
                  0}

véges automatával ekvivalens G reguláris nyelvtant!
 


Megoldás:
G=({q
                  0
                  ,q
                  1},{x,y},q
                  0
                  ,H),

                  H={ q
                  0 → xq
                  0
                  , q
                  0 → xq
                  1
                  , q
                  1 → yq
                  0
                  , q
                  1 → λ }. ★
 
 


5.33. példa - Ekvivalens reguláris nyelvtan megadása véges automatához 3. feladat


 Adjunk meg az A=({q
                  0,q
                  1,q
                  2},{x,y},q
                  0,δ,{q
                  2}),
 
 δ(q
                  0,x)={q
                  1}, δ(q
                  0,y)={q
                  2}, δ(q
                  1,x)={q
                  0,q
                  2},    
 δ(q
                  1,y)={q
                  1,q
                  2}, δ(q
                  2,x)={q
                  0}, δ(q
                  2,y)={q
                  1}
 
 véges automatával ekvivalens G reguláris nyelvtant!
 


Megoldás:
 G=({q
                  0
                  ,q
                  1
                  ,q
                  2},{x,y},q
                  0
                  ,H),
 H={ q
                  0 → xq
                  1
                  , q
                  0 → yq
                  2
                  , q
                  1 → xq
                  0
                  , q
                  1 → xq
                  2
                  , q
                  1 → yq
                  1,    
 q
                  1 → yq
                  2
                  , q
                  2 → xq
                  0
                  , q
                  2 → yq
                  1
                  , q
                  2 → λ }. ★
 
 


5.34. példa - Ekvivalens reguláris nyelvtan megadása véges automatához 4. feladat


Adjunk meg az A=({q
                  0
                  ,q
                  1
                  ,q
                  2
                  ,q
                  3},{x,y,z},q
                  0
                  ,δ,{q
                  0
                  ,q
                  2
                  ,q
                  3}),    
 
 δ(q
                  0
                  ,x)={q
                  1
                  ,q
                  3}, δ(q
                  0
                  ,y)={q
                  2}, δ(q
                  1
                  ,z)={q
                  0
                  ,q
                  2},    
 δ(q
                  2
                  ,x)={q
                  0}, δ(q
                  3
                  ,y)={q
                  1}.
 
 véges automatával ekvivalens G reguláris nyevtant!
 


Megoldás:
G=({q
                  0
                  ,q
                  1
                  ,q
                  2
                  ,q
                  3},{x,y,z},q
                  0
                  ,H),
H={ q
                  0 →  xq
                  1
                  , q
                  0 →  xq
                  3
                  , q
                  0 →  yq
                  2
                  , q
                  1 →  zq
                  0
                  , q
                  1 →  zq
                  2,
q
                  2 →  xq
                  0
                  , q
                  3 →  yq
                  1
                  , q
                  0 →  λ, q
                  2 → λ, q
                  3 → λ }. ★
 


5.35. példa - Ekvivalens véges automata megadása reguláris nyelvtanhoz 1. feladat

Adjunk meg a G=({S,A,B},{a,b},S,H) H={ S → abaB, A → B, Acacb, B → bA, BS, B → λ } nyelvtannal ekvivalens véges üresszóátmenet nélküli automatát!


Megoldás:

(I.) Első lépésben megadunk egy G 1 nyelvtant, ami ekvivalens a G nyelvtannal és nem szerepelnek benne Y → y 1 y 2 ... yn és Y → y 1 y 2 ... Yn , n ≥ 3 alakú szabályok. A H szabályhalmaz ilyen alakú szabályait helyettesítjük új szabályokkal, a többi szabályt pedig változtatás nélkül átvesszük a H 1 szabályhalmazba.

Minden Y → y 1 y 2 ... yn , n ≥ 3 alakú szabályhoz vezessünk be Z 1 ,Z 2 , ... ,Z n-1 új nemterminálisokat, Zi -ből fogjuk levezetni az y i+1 ... yn . Ehhez az összes Y → y 1 y 2 ... yn , n ≥ 3 alakú szabályt helyettesítsük a következő szabályokkal:



                  Y → y
                  1
                  Z
                  1
                  ,

                  Z
                  1
                   → y
                  2
                  Z
                  2
                  ,
.
.
.
Z
                  
                     n-2

                   → y
                  
                     n-1

                  Z
                  
                     n-1
,
Z
                  
                     n-1

                   → y
                  
                     n
                  
.

Minden Y → y
                  1
                  y
                  2
                   ... Yn
                  
n ≥ 3 alakú szabályhoz vezessünk be Z
                  1
                  ,Z
                  2
                  , ...,Z
                  
                     n-2
 új
nemterminálisokat. Zi
                  
-ből az y
                  
                     i+1
 ... yn
                  
 szót fogjuk levezetni:
az összes Y → y
                  1
                  y
                  2
                   ... Yn
                  
n ≥ 3 alakú szabályt helyettesítsük a következő szabályokkal:
 



                  Y → y
                  1
                  Z
                  1
                  ,

                  Z
                  1
                   → y
                  2
                  Z
                  2
                  ,
.
.
.
Z
                  
                     n-3

                   → y
                  
                     n-2

                  Z
                  
                     n-2

                  ,

                  Z
                  
                     n-2

                   → y
                  
                     n-1

                  Yn.

               

Jelen esetben:

{G 1 =({S,A,B,Z 1 ,Z 2 ,Z 3 ,Z 4 ,Z 5},{a,b},S,H 1). H 1 ={ S → aZ 1 , Z 1 → bZ 2 , Z 2  → aB, A → B, A  → cZ 3 , Z 3 → aZ 4 , Z 4 → cZ 5 , Z 5  → b, B → bA, B  → S, B → λ }

(II.) Második lépésben megadunk egy G ' nyelvtant, ami ekvivalens a G nyelvtannal és nem szerepelnek benne X → Z alakú szabályok. Ehhez két lépésre van szükség.

- Először meghatározunk egy U(Z) halmazt minden olyan Z nemterminálishoz, mely levezethető legalább egy másik nemterminálisból a G 1 nyelvtanban és szerepel olyan H 1 halmazban lévő szabály bal oldalán, amelynek jobb oldalán egy terminális, vagy egy terminális és egy nemterminális betű, vagy pedig az üresszó áll. Az U(Z) halmaz tartalmazni fogja az összes olyan nemterminálist, melyből egy vagy több lépésben levezethető a Z betű.


Jelen esetben:
U(B)={A},U(S)={B,A}.
 - Majd a H' szabályhalmazba átvesszük a H
                  1 szabályhalmaz
mindazon szabályait, melyek nem X → Z alakúak, majd hozzávesszük mindazon szabályokat,
melyeket úgy kapunk, hogy a már átvett szabályok bal oldalán szereplő betűt a hozzá tartozó
U halmaz elemeivel helyettesítjük.
 

Formálisan:

H 2 =(H 1∪{W  → p|Z → pH 1 ,WU(Z)})∖{X → Y|X,YN 1}.

Jelen esetben:

G'=({S,A,B,Z 1 ,Z 2 ,Z 3 ,Z 4 ,Z 5},{a,b},S,H'). H'={ S → aZ 1 , B → aZ 1 , A → aZ 1 , Z 1 → bZ 2 , Z 2  → aB, A → cZ 3 , Z 3 → aZ 4 , Z 4 → cZ 5 , Z 5  → b, B → bA, A  → bA, B → λ, A → λ }

(III.) Harmadik lépésben megadjuk a G nyelvtannal ekvivalens A véges automatát. Az A automata állapothalmazát úgy kapjuk, hogy a G' nyelvtan nemterminálisainak a halmazához hozzáadunk egy új qv állapotot. Az automata bemenő jeleinek a halmaza megegyezik a G nyelvtan terminálisainak a halmazával, a kezdőállapota a startszimbólum lesz, a végállapotok halmaza pedig tartalmaz minden olyan X állapotot, mely szerepelt X → λ alakú szabályban, valamint tartalmazza az újonnan bevezett qv állapotot is.


Az A automata  δ átmenetfüggvényét úgy kapjuk, hogy minden H' halmazban szereplő X → yZ
szabály esetén felvesszük a δ(X,y)=Z átmenetet, valamint az X → y alakú szabályok esetén
a δ(X,y)=qv
                  
 átmenetet.

Jelen esetben:
A=({S,A,B,Z
                  1
                  ,Z
                  2
                  ,Z
                  3
                  ,Z
                  4
                  ,Z
                  5
                  ,qv
                  
},{a,b},S,δ,{B,A,qv
                  
}).


                  δ(S,a)={Z
                  1}, δ(B,a)={Z
                  1}, δ(A,a)={Z
                  1}, δ(Z
                  1
                  ,b)={Z
                  2}, δ(Z
                  2
                  ,a)={B}, δ(A,c)={Z
                  3},

                  δ(Z
                  3
                  ,a)={Z
                  4}, δ(Z
                  4
                  ,c)={Z
                  5}, δ(Z
                  5
                  ,b)={qv
                  
}, δ(B,b)={A}, δ(A,b)={A} ★
 
 

5.36. példa - Ekvivalens véges automata megadása reguláris nyelvtanhoz 2. feladat


Adjunk meg a G=({S,A,B},{x,y},S,H)
H={ S → xA, S → yyB, A → B, B → yS, B → xyx, B → λ }

nyelvtannal ekvivalens véges automatát!


Megoldás:
(I.)
G
                  1
                  =({S,A,B,Z
                  1
                  ,Z
                  2
                  ,Z
                  3},{x,y},S,H
                  1).

                  H
                  1
                  ={ S → xA, S → yZ
                  1
                  , Z
                  1
                   → yB, A → B,

                  B → yS, B → xZ
                  2
                  , Z
                  2
                   → yZ
                  3
                  , Z
                  3
                   → x,

                  B → λ }

(II.)
U(B)={A}.

                  G'=({S,A,B,Z
                  1
                  ,Z
                  2
                  ,Z
                  3},{a,b},S,H').

                  H'={ S → xA, S → yZ
                  1
                  , Z
                  1
                   → yB, B → yS,A → yS,

                  B → xZ
                  2
                  ,A → xZ
                  2
                  , Z
                  2
                   → yZ
                  3
                  , Z
                  3
                   → x, B → λ,A → λ }

(III.)
A=({S,A,B,Z
                  1
                  ,Z
                  2
                  ,Z
                  3
                  ,qv
                  
},{x,y},S,δ,{B,A,qv
                  
}).


                  δ(S,x)={A}, δ(S,y)={Z
                  1}, δ(Z
                  1
                  ,y)={B}, δ(B,y)={S}, δ(A,y)={S},

                  δ(B,x)={Z
                  2}, δ(A,x)={Z
                  2}, δ(Z
                  2
                  ,y)={Z
                  3}, δ(Z
                  3
                  ,x)={qv
                  
} ★
 
 


5.37. példa - Ekvivalens véges automata megadása reguláris nyelvtanhoz 3. feladat


Adjunk meg a G=({S,A,B},{x,y},S,H)
H={ S → xA, S → yB, S → B, B → A, A → xS, A → y }
nyelvtannal ekvivalens véges automatát!

Megoldás:
(I.)
Mivel a G nyelvtanban nincs Y → y
                  1
                  y
                  2
                   ... yn
                  
 és Y → y
                  1
                  y
                  2
                   ... Yn
                  
n ≥ 3 alakú szabály, ezért
G
                  1
                  =G.

(II.)
U(A)={B,S}.

                  G'=({S,A,B},{x,y},S,H').

                  H'={ S → xA, S → yB, A → xS, B → xS, S → xS, A → y, B → y, S → y }

(III.)
A=({S,A,B,qv
                  
},{x,y},S,δ,{qv
                  
}).


                  δ(S,x)={A}, δ(S,y)={B}, δ(A,x)={S}, δ(B,x)={S},

                  δ(S,x)={S}, δ(A,y)={qv
                  
}, δ(B,y)={qv
                  
}, δ(S,y)={qv
                  
} ★

 


5.38. példa - Ekvivalens véges automata megadása reguláris nyelvtanhoz 4. feladat


 
Adjunk meg a G=({S,A,B},{x,y},S,H)
H={ S → xxxA, S → yyyB, A → yS, B → xS, A → xx, B → yy }

nyelvtannal ekvivalens véges automatát!

Megoldás:
(I.)
G'=({S,A,B,Zv,Z
                  2
                  ,Z
                  3
                  ,Z
                  4
                  ,Z
                  5
                  ,Z
                  6},{x,y},S,H').

                  H'={ S → xZ
                  1
                  , Z
                  1
                   → xZ
                  2
                  , Z
                  2
                   → xA, S → yZ
                  3
                  , Z
                  3
                   → yZ
                  4
                  , Z
                  4
                   → yB,

                  A → yS, B → xS, A → xZ
                  5
                  , Z
                  5
                   → x, B → yZ
                  6
                  , Z
                  6
                   → y }

(II.)
Mivel a G
                  1 nyelvtanban nincs X → Z alakú szabály, ezért G
                  2
                  =G
                  1.

(III.)
A=({S,A,B,Z
                  1
                  ,Z
                  2
                  ,Z
                  3
                  ,Z
                  4
                  ,Z
                  5
                  ,Z
                  6
                  ,qv
                  
},{x,y},S,δ,{qv
                  
}).


                  δ(S,x)={Z
                  1}, δ(Z
                  1
                  ,x)={Z
                  2}, δ(Z
                  2
                  ,x)={A}, δ(S,y)={Z
                  3}, δ(Z
                  3
                  ,y)={Z
                  4}, δ(Z
                  4
                  ,y)={B},

                  δ(A,y)={S}, δ(B,x)={S}, δ(A,x)={Z
                  5}, δ(Z
                  5
                  ,x)={qv
                  
}, δ(B,y)={Z
                  6}, δ(Z
                  6
                  ,y)={q
                  1} ★

 


5.39. példa - Ekvivalens véges automata megadása reguláris nyelvtanhoz 5. feladat


 
Adjunk meg a G=({S,X,Y},{x,y,z},S,H)

H={ S → xX, S → z, S → λ, X → yY, X → zS, X → x, Y → xX, Y → y, }

nyelvtannal ekvivalens véges automatát!
 



Megoldás:

(I.)
Mivel a G nyelvtanban nincs Y → y
                  1
                  y
                  2
                   ... yn
                  
 és
Y → y
                  1
                  y
                  2
                   ... Yn
                  
n ≥ 3 alakú szabály, ezért G
                  1
                  =G.

(II.)
Mivel a G
                  1 nyelvtanban nincs X → Z alakú szabály, ezért G
                  2
                  =G
                  1.

(III.)
 A=({S,X,Y,qv
                  
},{x,y,z},S,δ,{S,qv
                  
}).

δ(S,x)={X}, δ(S,z)={qv
                  
}, δ(X
                  ,y)={Y}, δ(X,x)={qv
                  
}, δ(X,z)={S}, δ(Y
                  ,y)={qv
                  
}, δ(Y,x)={X} ★

 


5.40. példa - Ekvivalens véges automata megadása reguláris nyelvtanhoz 6. feladat


Adjunk meg a G=({S,A},{0,1},S,H)
H={ S → 0, S → 1A, A → 0A, A → 1A, A → λ }

nyelvtannal ekvivalens véges automatát!

Megoldás:
(I.)
Mivel a G nyelvtanban nincs Y → y
                  1
                  y
                  2
                   ... yn
                  
 és Y → y
                  1
                  y
                  2
                   ... Yn
                  
n ≥ 3
alakú szabály, ezért G
                  1
                  =G.

(II.)
Mivel a G
                  1 nyelvtanban nincs X → Z alakú szabály, ezért G
                  2
                  =G
                  1.

(III.)
A=({S,A,qv
                  
},{0,1},S,δ,{A,qv
                  
}).


                  δ(S,0)={qv
                  
}, δ(S,1)={A}, δ(A,0)={A}, δ(A,1)={A} ★
 


5.41. példa - Ekvivalens véges automata megadása reguláris nyelvtanhoz 7. feladat


Adjunk meg a G=({S,A},{0,1,+,-},S,H)
H={ S → 0, S → 1A, S → -1A, A → 0A,

                  A → 1A, A → λ, A → +1A, A → -1A }

nyelvtannal ekvivalens véges automatát!

Megoldás:

(I.)
G
                  1
                  =({S,A,Z
                  1
                  ,Z
                  2
                  ,Z
                  3},{0,1,+,-},S,H)
H={ S → 0, S → 1A, S → -Z
                  1
                  , Z
                  1
                   → 1A, A → 0A, A → 1A,

                  A → λ, A → +Z
                  2
                  , Z
                  2
                   → 1A, A → -Z
                  3
                  , Z
                  3
                   → 1A }

(II.)
Mivel a G
                  1 nyelvtanban nincs X → Z alakú szabály, ezért G
                  2
                  =G
                  1.

(III.)
A=({S,A,Z
                  1
                  ,Z
                  2
                  ,Z
                  3
                  ,qv
                  
},{0,1},S,δ,{A,qv
                  
}).


                  δ(S,0)={qv
                  
}, δ(S,1)={A}, δ(S,-)={Z
                  1}, δ(Z
                  1
                  ,1)={A}, δ(A,0)={A},

                  δ(A,1)={A}, δ(A,+)={Z
                  2}, δ(Z
                  2
                  ,1)={A}, δ(A,-)={Z
                  3}, δ(Z
                  3
                  ,1)={A} ★