online kép - Fájl  tubefájl feltöltés file feltöltés - adja hozzá a fájlokat onlinefedezze fel a legújabb online dokumentumokKapcsolat
  
 

Letöltheto dokumentumok, programok, törvények, tervezetek, javaslatok, egyéb hasznos információk, receptek - Fájl kiterjesztések - fajltube.com

 

Online dokumentumok - kep
  

Veremautomatak és kapcsolatuk a környezetfüggetlen nyelvtanokkal

számítógépes

Fájl küldése e-mail



egyéb tételek

 
Az Excel diagramjai
Network Monitor A halózati forgalom elemzése - 1. rész, elméleti alapok
Szemaforok
A Pascal program szerkezete
Képszerkesztők, vektorgrafikus programok
A CLIPPER relaciós adatbaziskezelő nyelv
Az oracle sql
10 hasznos tipp PhotoShop-hoz
Különlegességek
 
 

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


Veremautomaták


   a1      a2          .............................         ak-1     ak         ............                   bemenő szalag





                     121b13b                      121b13b                 

                     121b13b                      121b13b           véges állapotú

                     121b13b                      121b13b              vezérlőmű



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





                     121b13b                      121b13b           z1      z2          .............................         zl-1     zk         ...............



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, q0, z0, 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*

              - q0 A   kezdőállapot

              - z0 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= a1,a2.....ak, g=x1, ....., xm; gi W*

     Ha (pi, gi d(q,a1,xm), akkor <q, a1a2...ak, x1...xm-1xm> ¾ <pi,a2a3...ak, x1...xm-1gi>

     Ha (pi, gi d(q,e,xm), akkor <q, a1a2...ak, x1...xm-1xm> ¾ <pi, a1...ak, x1... xm-1,gi>

Működés: b1b2...be bemenő szó hatására

Kezdeti konfiguráció: <q0, b1...be, z0>

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     M1=< d,q0,z0, >

d(q0,e,z1)=                      121b13b                      121b13b                      121b13b                  (a,z1/z1z1)

d(q0,a,z0)=                      121b13b                    (a,z0/z0z1)            q1

d(q1,a,z1)=                      121b13b               q0

d(q1,b,z1)=                      121b13b   (e,z0/e)                     121b13b              (b,z1,e

d(q2,b,z1)=                      121b13b                      121b13b    (e,z0/e)  q2

d(q2,e,z0)=                      121b13b                      121b13b                      121b13b   (b,z1/e


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

                     121b13b                      121b13b                      121b13b         <q0,aabb,z0>




                     121b13b                   <q0,aabb,e>                     121b13b                 <q1,abb,z0z1>


                     121b13b                      121b13b                      121b13b                      121b13b             <q1,bb,z0z1z1>


                     121b13b                      121b13b                      121b13b                      121b13b                <q2,b,z0z1>


                     121b13b                      121b13b                      121b13b                      121b13b                  <q2,e,z0>


                     121b13b                      121b13b                      121b13b                      121b13b                  <q0,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 M1 nemdetermináns veremautomata ¾ üres veremmel        felismerni L nyelvet Û létezik M2 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 dX1 ... Xk, ahol d T; X,X1, ..., Xk 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 aI-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.




: 882