Beágyazott akkumulátor-automata
Az automata elméletben a beágyazott verem automaták olyan véges automaták, amelyek kiegészítő memóriaként olyan veremeket használnak, amelyek elemei maguk is halmok lehetnek. De a szokásos akkumulátoros automatákkal ellentétben a beágyazott veremautomaták előre és hátra mozoghatnak a „verem” -en, amely ezért inkább egy listában van felépítve; ezenkívül az automata behelyezhet egy új elemet, működtetheti azt, megsemmisítheti és folytathatja a munkát a régi akkumulátorral. Ez az üzemmód rekurzívan beágyazható tetszőleges mélységben; a vezérlő azonban mindig a legbelső köteget kezeli.
A beágyazott verem automaták képesek indexelt nyelv felismerésére , és az indexelt nyelvek pontosan azok a nyelvek, amelyeket a nemdeterminisztikusan beágyazott halmozott automaták ismernek fel.
A beágyazott akkumulátoros PLC-k eltérnek a fedélzeti akkumulátoros PLC-ktől, amelyek kevésbé hatékonyak, mivel utóbbiak esetében a mindig rekurzívan szervezett segédmemória csak a verem tetejéről érhető el. A fedélzeti verem automaták pontosan felismerik azokat a nyelveket, amelyeket a kiegészítő fa nyelvtanok generálnak .
Informális leírás
Egy beágyazott akkumulátoros vezérlő beolvassa adatait egy bemeneti szalagról; a beviteli szó nem módosítható, két marker határolja, és kétirányú esetben az olvasófej előre és hátra mozoghat a beviteli szalagon; egyirányú beágyazott PLC-k esetén a bemenő szó olvasási feje nem mehet vissza.
Az automata halmazokból áll
-
Q,Σ{\ displaystyle Q, \ Sigma}, És amelyek a bemeneti szimbólumok és a szimbólumköteg állapotainak véges halmazai ;Γ{\ displaystyle \ Gamma}
- A markerek , rögzített , és a ; ezek további szimbólumok, amelyeket jelölőként használnak a verem szavainak kezdetére vagy végére;${\ displaystyle \ $}¢{\ displaystyle {\ text {¢}}}#{\ displaystyle \ #}
- átmeneti szabályok összessége, amelyek lehetővé teszik az olvasófej mozgását a bemeneti szalagon, valamint az olvasási és írási fej mozgását a veremben.
A veremnek nevezett kiegészítő memória valójában egy lineáris szerkezet, ahol a veremfej mindkét irányban mozoghat. A verem egy fa szerkezet kódolása: elemei vagy a verem ábécé szimbólumai, vagy maguk a veremek, amelyeket lineárisan ábrázolnak a kezdő és a vég verem jelölőkkel. Az akkumulátorok maguk is tartalmazhatnak elemeket. A verem általában a következő lineáris formát öltheti:
Γ{\ displaystyle \ Gamma}
$nál nélb$k¢$o_¢¢vs.¢#{\ displaystyle \ $ \, a \, b \, \ $ \, k \, {\ text {¢}} \, {\ aláhúzás {\ $ \, p}} {\ text {¢}} \, { \ text {¢}} \, c \, {\ text {¢}} \ #}Ha több olvashatóság, akkor cserélje ki a markereket , a nyitó és záró zárójelek és kihagyja a marker , megkapjuk az írás:
${\ displaystyle \ $}¢{\ displaystyle {\ text {¢}}}#{\ displaystyle \ #}
(nál nélb(k)(o_)vs.){\ displaystyle \, (\, a \, b \, (\, k \,) \, {\ aláhúzás {(\, p}} \,) \, c \,)}A verem tartalmazza a verem ábécé elemeit , majd az elemre redukált alhalmot, majd egy második alköteget, amely végül a betűből áll . Az író-olvasó fej az alhalmaz elején helyezkedik el , amelyet aláhúzás képvisel.
nál nél,b{\ displaystyle a, b}k{\ displaystyle k}o{\ displaystyle p}vs.{\ displaystyle c}(o){\ displaystyle (p)}
Példa
Itt látható a műveletek sorrendje és azok hatása a veremre. A 2. lépésben egy verem jön létre az alverem belsejében ; ez az al-alverem az . Ezután fokozatosan kiürül, majd az 5. lépésben megsemmisül. A 8. lépésben a verem írási feje a kezdeti szinten van, és egy egyszerű beszúrás hozzáadja a szimbólumokat .
(o){\ displaystyle (p)}(rs){\ displaystyle (rs)}nem,o{\ displaystyle n, o}
n °
|
akció
|
akkumulátor
|
---|
1:
|
|
(nál nélb(k)(o_)vs.){\ displaystyle \, (\, a \, b \, (\, k \,) \, {\ aláhúzás {(\, p}} \,) \, c \,)}
|
2:
|
alverem létrehozása
|
(nál nélb(k)(o(r_s))vs.){\ displaystyle \, (\, a \, b \, (\, k \,) \, (\, p \, {\ aláhúzás {(\, r}} \, s \,) \,) \, vs)}
|
3:
|
pop
|
(nál nélb(k)(o(s_))vs.){\ displaystyle (\, a \, b \, (\, k \,) \, (\, p \, {\ aláhúzás {(\, s}} \,) \,) \, c \,)}
|
4:
|
pop
|
(nál nélb(k)(o(_))vs.){\ displaystyle (\, a \, b \, (\, k \,) \, (\, p \, {\ aláhúzás {(}} \,) \,) \, c)}
|
5:
|
alverem megsemmisítése
|
(nál nélb(k)(o)_vs.){\ displaystyle (\, a \, b \, (\, k \,) \, (\, p \, {\ aláhúzás {)}} \, c \,)}
|
6:
|
Származás
|
(nál nélb(k)(o)vs._){\ displaystyle (\, a \, b \, (\, k \,) \, (\, p \,) \, {\ aláhúzás {c}} \,)}
|
7:
|
mászik
|
(nál nélb(k)(o)_vs.){\ displaystyle (\, a \, b \, (\, k \,) \, (\, p \, {\ aláhúzás {)}} \, c \,)}
|
8:
|
mászik
|
(nál nélb(k)(o_)vs.){\ displaystyle \, (\, a \, b \, (\, k \,) \, {\ aláhúzás {(\, p}} \,) \, c \,)}
|
9:
|
nyom
|
(nál nélb(k)(nem_oo)vs.){\ displaystyle \, (\, a \, b \, (\, k \,) \, {\ aláhúzás {(\, n}} \, o \, p \,) \, c \,)}
|
Az átmeneti szabályok hivatalos leírása összetett, mivel figyelembe kell vennie a verem szimbólumait és a verem fa szerkezetét.
Tulajdonságok
Meghatározhatunk kétirányú beágyazott verem automatákat , és megmutathatjuk, hogy ez nem növeli a számítási teljesítményt a szokásos kétirányú verem automatákhoz képest.
Robert Gilman és Michael Shapiro használt beágyazott elem automaták, hogy megoldja a szót probléma bizonyos csoportok .
Megjegyzések és hivatkozások
(en) Ez a cikk részben vagy egészben az
angol Wikipedia
" Beágyazott verem automatája " című cikkéből származik
( lásd a szerzők felsorolását ) .
-
Alfred Aho , „ Beágyazott verem automaták ”, Journal of the ACM , vol. 16, n o 3,1969, P. 383–406 ( DOI 10.1145 / 321526.321529 , online olvasás )
-
Barbara Parteea, Alice ter Meulen és Robert E. Wall, Matematikai módszerek a nyelvészetben , Kluwer Academic Publishers,
1990, 666 p. ( ISBN 978-90-277-2245-4 , online előadás ).
-
Bevezetés az automata elméletbe, a nyelvekbe és a számításba , Addison-Wesley,
1979, 418 p. ( ISBN 978-0-201-02988-8 ). Ebben a könyvben a 390. oldalon.
-
Laura Kallmeyer, a szövegkörnyezet nélküli nyelvtanok elemzése , Springer,2010, xii + 247 o. ( ISBN 978-3-642-14845-3 , DOI 10.1007 / 978-3-642-14846-0 ).
-
C. Beeri, „ Two-Way Beágyazott Stack automaták egyenértékű a két-utas Stack Automata ”, J. Comp. és System Sciences , vol. 10,1975, P. 317–339 ( DOI 10.1016 / s0022-0000 (75) 80004-3 , online olvasás )
-
Robert Gilman, Michael Shapiro, " Olyan csoportokról, amelyeknek a szóproblémáját egy beágyazott verem automata oldja meg ", - oldal = 16 ,1998( arXiv 9812028v1.pdf , online olvasás )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">