Czy istnieją warianty widocznych automatów przesuwających, które umożliwiają wypychanie słów na stos?

Zastanawiam się, czy są jakieś dokumenty lub badania dotyczące widocznych automatów przesuwających w dół, ale pozwalające na wypychanie słów zamiast pojedynczych liter na stos.

Alternatywnie, konstrukcja umożliwiająca wypychanie symboli na -transitions może osiągnąć ten sam cel. $\epsilon$

Oczywiście, takie warianty mogą być tworzone, ale zastanawiam się, czy to rujnuje właściwości zamknięcia i rozstrzygalności, które czynią VPA interesującymi.

Patrzę na konstrukcję, w której stos jest licznikiem, zwiększając go o stałe na podstawie odczytanych początkowych symboli, a następnie odliczając na podstawie odczytanych innych symboli.

Dla każdego, kto nie wie, widoczne automaty wypychające to takie, w których alfabet można podzielić na symbole popping, popping symbole i symbole, które w ogóle nie wpływają na stos. Wybór wypychania zamiast popychania jest całkowicie zdeterminowany przez odczytany bieżący symbol. Są zamknięte pod skrzyżowaniem, zjednoczeniem, konkatenacją, gwiazdą i dopełnieniem, co daje im bogactwo decydujących właściwości. Zobacz ten artykuł, aby uzyskać więcej.

reference-request fl.formal-languages automata-theory context-free context-free-languages jmite
źródło

wydaje się oczywistym pytaniem jest, czy takie automaty są równoważne ze standardowymi automatami pushdown z „słowami” zamienionymi na sekwencje stanów? afaik, tak? jeśli nie, pomocny byłby przykładowy przykład przypadku, w którym zawodzi.

vzn

@vzn Nie mogą być równoważne. Te wyraźnie PDA wydają się być zdecydowanie słabsze. Ostatnim razem, gdy sprawdzałem, CFL-y nie były zamknięte na skrzyżowaniu.

Kai

Tak więc, VPDAs są zamknięte pod skrzyżowania, i są znane jako odpowiednio pomiędzy

. Nie mam jednak pojęcia, czy mój wariant jest zamknięty pod skrzyżowaniem, więc może być równoważny. Wątpię, ale nie jestem pewien.

R E G

$REG$

D C F L

$DCFL$

jmite

W tym dokumencie dx.doi.org/10.1145/1516512.1516518 przedstawiono charakterystykę gramatyczną VPDA i konstrukcję do konwersji między gramatykami i VPDA. Być może gramatyka może służyć do symulowania wypychania całych słów?

Evgenij Thorstensen

Dlaczego naciśnięcie słowa na symbol jest równoznaczne z zezwoleniem na naciśnięcia na przejścia eps?

domotorp

Odpowiedzi:

Z epsilon popycha

W przypadku wersji z przejściem na epsilon-przejścia dowód nierozstrzygalności uniwersalności automatów pushdown można dostosować do tego nowego ustawienia, dlatego tracimy co najmniej następujące właściwości: zamknięcie w uzupełnieniu, możliwość określenia, rozstrzygalność o uniwersalności i włączeniu.

Schemat dowodowy: weź maszynę Turinga , chcemy zbudować VPA z epsilon-push, tak aby była uniwersalna tylko wtedy, gdy M nie ma akceptowalnego przebiegu. $M$ $A$

Projektujemy tak, że słowo nie przyjął wtedy i tylko on jest w postaci: $A$

gdzie

# C_{0} & C_{0} $ (\bar{C_{0}})^{R} # C_{1} & C_{1} $ (\bar{C_{1}})^{R} # C_{2} & C_{2} $ (\bar{C_{2}})^{R} \dots # C_{n} & C_{n} $ (\bar{C_{n}})^{R}

$\#C_0\&C_0\$(\overline{C_0})^R\#C_1\&C_1\$(\overline{C_1})^R\#C_2\&C_2\$(\overline{C_2})^R\dots\#C_n\&C_n\$(\overline{C_n})^R$

Każde koduje prawidłową konfigurację $C_i$ $M$
jest początkowe, akceptuje $C_0$ $C_n$
jest odwrotnością słowa $u^R$ $u$
jest kopiąużyciu pop liter $\overline{u}$ $u$
to specjalne symbole separacji spoza alfabetu $\#,\&,\$$ $M$
jest zawsze prawidłowym przejściem $C_i\to C_{i+1}$ $M$

VPA jest zmuszona wyskoczyć na czynniki o postaci . może nie deterministycznie odgadnąć naruszenie którejkolwiek z właściwości i zweryfikować je. Kluczem jest to, że może albo naciskać na , albo nic nie robić, co pozwala zweryfikować wszystkie warunki (właściwie odgadnąć ich naruszenia). W szczególności, może on zgadywać, że pierwsze (lub drugie) Występowanie nie odpowiada , pomijając drugi składnik. Może także zgadywać, że $A$ $C_i^R$ $A$ $C_i$ $C_i$ $(\overline{C_i})^R$ $C_i\to C_{i+1}$ nie jest poprawnym przejściem, wypychając oba wystąpienia , a następnie popping jedno, nie wciskając i porównując z zawartością stosu. Dla innych , które nie są częścią typowania, jeden składnik jest popychany i jest zdejmowana. $C_i$ $C_{i+1}$ $(\overline{C_{i+1}})^R$ $C_j$ $(\overline{C_j})^R$

Pchanie słów

Jeśli chodzi o warianty, w których słowa są wypychane, wydaje się, że dowód determinowalności w oryginalnej pracy na temat VPA można dostosować do tego ustawienia. Wystarczy dostosować konstrukcję, aby symbole stosu miały postać gdzie jest przedrostkiem słowa, które można wypchnąć zgodnie z funkcją przejścia. Gdy pojawiały się w , znajduje się w pozycji $(S,R,u)$ $u\in A^*$ $a$ $(S,R,va)$ $(S',R',v)$ $S'$ $R'$

Denis
źródło