online kép - Fájl  tube fájl feltöltés file feltöltés - adja hozzá a fájlokat online fedezze fel a legújabb online dokumentumok Kapcsolat
   
 

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
   
kategória
 

Biológia állatok Fizikai Földrajz Kémia Matematika Növénytan Számítógépes
Filozófia
Gazdaság
Gyógyszer
Irodalom
Menedzsment
Receptek
Vegyes

 
 
 
 













































 
 

Veremautomatak és kapcsolatuk a környezetfüggetlen nyelvtanokkal

számítógépes

Fájl küldése e-mail Esszé Projekt


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*

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

2.      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

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

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

3. 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-1> pár legyen eleme d(q,e,A)-nak.

                     121b13b                     (a-1 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:

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

       2. w-t olvasva egyenként törli a-1 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.

 

 


: 735