Veremautomatak és kapcsolatuk a környezetfüggetlen nyelvtanokkal

Veremautomaták és kapcsolatuk a környezetfüggetlen nyelvtanokkal.

Veremautomaták

   a₁      a₂          .............................         a_k-1     a_{k         ............}                   bemenő szalag

                     121b13b                      121b13b                 

                     121b13b                      121b13b           véges állapotú

                     121b13b                      121b13b              vezérlőmű

                     121b13b                      121b13b                      121b13b                      121b13b                      121b13b                      121b13b         veremmemória

                     121b13b                      121b13b           z₁      z₂          .............................         z_l-1     z_{k         ...............}

Működés:

-   Bekapcsoláskor a vezérlőmű egy rögzített kezdőállapotba kerül, veremmemóriában egy rögzített kezdőjel van.

-   Lehetséges lépések:

              - beolvas egy bemenő jelet. Ettől és az aktuális belső állapotától függően új állapotba

                 kerül és beír egy szót a veremmemóriába a beolvasott felső jel helyére.

              - bemeneti jel beolvasása nélkül, a memória legfelső jelétől függően kerül új állapotba, és

                 ír egy szót a veremmemóriába. (e-lépés)

-   Megállás:

              - nincs definiált lépés

              - kiürült a verem

Végállapottal való felismerés: egy bemenő szó hatására létezik-e olyan működés, mellyel végállapotba jutunk? (nemdeterminisztikus automata)

Üres veremmel való felismerés:  van-e olyan működés, melynek hatására a verem kiürül?

M nemdeterminisztikus veremautomata, ha M=<A, V, W, d, q₀, z₀, F>, ahol:

              - A         belső állapotok véges, nem üres halmaza

              - V         bemenő ábécé

              - W        veremábécé

d          átmenetfüggvény : d:A (VÈ W A W*

              - q₀ A   kezdőállapot

              - z₀ W  kezdőjel (a veremmemóriában)

              - F A    végállapotok halmaza

M nemdeterminisztikus veremautomata konfigurációi az <q,a g> hármasok, ahol q A, a V*, g W*.

Konfigurációk átvitele egymásba:

a= a₁,a₂.....a_k, g=x₁, ....., x_m; g_i W*

     Ha (p_i, g_i d(q,a₁,x_m), akkor <q, a₁a₂...a_k, x₁...x_m-1x_m> ¾ <p_i,a₂a₃...a_k, x₁...x_m-1g_i>

     Ha (p_i, g_i d(q,e,x_m), akkor <q, a₁a₂...a_k, x₁...x_m-1x_m> ¾ <p_i, a₁...a_k, x₁... x_m-1,g_i>

Működés: b₁b₂...b_e bemenő szó hatására

Kezdeti konfiguráció: <q₀, b₁...b_e, z₀>

d-val meghatározzuk az összes lehetséges konfigurációt, amibe az eredeti átvihető.

Az összes új konfigurációkra meghatározzuk a lehetséges új konfigurációkat, stb ...

Felismer egy szót végállapottal:   ha a sorozat utolsó elemei között létezik <p,e g> típusú,

                     121b13b                      121b13b               ahol p F.

Felismer egy szót üres veremmel: ha a sorozat utolsó elemei között létezik <p,e e> típusú. ( p nem                      121b13b                      121b13b    feltétlen eleme F-nek)

M által végállapottal felismert nyelv  - T(M) -  azon szavak halmaza, melyeket M végállapottal felismer.

M által üres veremmel felismert nyelv  - N(M) -  azon szavak halmaza, melyet M üres veremmel ismer fel.

Példa     M₁=< d,q₀,z₀, >

d(q₀,e,z₁)=                      121b13b                      121b13b                      121b13b                  (a,z₁/z₁z₁)

d(q₀,a,z₀)=                      121b13b                    (a,z₀/z₀z₁)            q₁

d(q₁,a,z₁)=                      121b13b               q₀

d(q₁,b,z₁)=                      121b13b   (e,z₀/e)                     121b13b              (b,z₁,e

d(q₂,b,z₁)=                      121b13b                      121b13b    (e,z₀/e)  q₂

d(q₂,e,z₀)=                      121b13b                      121b13b                      121b13b   (b,z₁/e

A konfigurációk átmenetei az   aabb  bemeneti szó hatására:

                     121b13b                      121b13b                      121b13b         <q₀,aabb,z₀>

                     121b13b                   <q₀,aabb,e>                     121b13b                 <q₁,abb,z₀z₁>

                     121b13b                      121b13b                      121b13b                      121b13b             <q₁,bb,z₀z₁z₁>

                     121b13b                      121b13b                      121b13b                      121b13b                <q₂,b,z₀z₁>

                     121b13b                      121b13b                      121b13b                      121b13b                  <q₂,e,z₀>

                     121b13b                      121b13b                      121b13b                      121b13b                  <q₀,e e>

Végállapottal és üres veremmel is felismerte az aabb szót.

A felismert nyelv: T(M)=N(M)=

Tétel     Tetszőleges L nyelvhez létezik M₁ nemdetermináns veremautomata ¾ üres veremmel        felismerni L nyelvet Û létezik M₂ nemdetermináns veremautomata ¾  végállapottal   ismeri fel az L nyelvet.

Azt a folyamatot, mellyel megállapítjuk egy adott szóról, hogy egy adott grammatika generálja-e, szintaktikus elemzésnek nevezzük.

G egy tetszőleges környezetfüggetlen grammatika. G szintaktikus elemzői olyan automaták, melyek tetszőleges w-ról eldöntik, hogy w L(G) vagy nem és megadják w szó G-beli levezetési fáit is.

Megjegyzés    A továbbiakban olyan második típusú nyelvtanokkal foglalkozunk, ahol a szabályok       alakja: X dX₁ ... X_k, ahol d T; X,X₁, ..., X_k N.

Állítás   Minden második típusú nyelvtanhoz létezik vele ekvivalens , a fenti alakú második típusú    nyelvtan.

Példa              G=< ,S, >

                     121b13b     Szintaktikus elemzés a baaa szó esetén:

                     121b13b                  S                     121b13b                      121b13b                      121b13b              S

                     121b13b bA                     121b13b    bSA                     121b13b                      121b13b        b       S       A

                     121b13b                      121b13b                      121b13b          Ebből a

                     121b13b baS                     121b13b   baA                     121b13b                      121b13b                  a        a        S

                     121b13b                      121b13b                      121b13b      levezetési fa.

                     121b13b baa                     121b13b   baaS                     121b13b                      121b13b                      121b13b                 a

                     121b13b                      121b13b         baaa

Tétel     G=<T, N, S, P> tetszőleges környezetfüggetlen grammatika. Ekkor létezik M               nemdeterminisztikus veremautomata ¾ üres veremmel felismeri az L(G) nyelvet.

Bizonyítás      Konstruktív

                     121b13b     Tegyük fel, hogy eÏL(G)

                     121b13b     A veremautomata legyen a következő: M=< , T, TÈN, d, q, S, Æ> ,  ahol                      121b13b     qÏTÈN és d a következő:

                     121b13b                   - minden P-beli A a szabályra <q,a > pár legyen eleme d(q,e,A)-nak.

                     121b13b                     (a az a tükörképe)

                     121b13b                   - minden a T-re d(q,a,a)=

Példa         Az előbbi grammatikához tartozó M nemdeterminisztikus veremautomata, mely üres   veremmel felismeri az L(G) nyelvet: M=< d, q, S, Æ>

                     121b13b         d(q,e,S)=

                     121b13b         d(q,e,A)=

                     121b13b         d(q,a,a)=

                     121b13b         d(q,b,b)=

A baaa szó  szintaktikus elemzése:

                     121b13b                      121b13b         <q,baaa,S>

<q,baaa,a>                     121b13b        <q,baaa,ASb>                     121b13b              <q,baaa,Ab>

                     121b13b                      121b13b        <q,aaa,AS>                     121b13b                  <q,aaa,A>

                     121b13b     <q,aaa,Aa> <q,aaa,AASb> <q,aaa,AAb> <q,aaa,b> <q,aaa,Sa>

                     121b13b       <q,aa,A>                     121b13b                      121b13b                      121b13b                      121b13b           <q,aa,S>

                     121b13b       <q,aa,b> <q,aa,Sa>                     121b13b <q,aa,a> <q,aa,ASb> <q,aa,Ab>

                     121b13b                      121b13b            <q,a,S>                     121b13b    <q,a,e>

                     121b13b             <q,a,a> <q,a,ASb> <q,a,Ab>

                     121b13b             <q,e e>

Tehát M üres veremmel,felismeri a baaa szót. A levezetési fa (baaa)^-1 =aaab -hez:

                     121b13b                      121b13b                      121b13b      S

                     121b13b                      121b13b       A                 S                 b

                     121b13b             S            a                 a

                     121b13b             a

Tehát a működés általában egy w szó esetén:

e-lépéssel kicseréli S-t a -gyel, ha létezik S a szabály.

w-t olvasva egyenként törli a utolsó elemeit, ha azok megegyeznek w beolvasott jeleivel.

       3. Ha nemdeterminisztikus jelhez (pl. A) ér, helyettesíti a^I-1 -gyel, ha A a P.

       4. Ha nem tud továbblépni, a fának ez az ága nem folytatható visszalép.

       5. Ha a veremmemória kiürül, akkor M felismeri w-t.