Czy DPDA bez ruchów

W formalnym opisie deterministycznych automatów wypychających pozwalają one na ruchy , w których maszyna może wyskakiwać lub pchać symbole na stos bez odczytywania symbolu z wejścia. Jeśli te ruchy są niedozwolone, a stos można zmodyfikować tylko raz po odczytaniu każdego symbolu, czy wynikowe automaty są równe mocy DPDA? $\epsilon$ $\epsilon$

Może być coś trywialnego, czego mi brakuje w odniesieniu do używania zestawu mocy jako nowego , co pozwala na „kompresowanie” ruchów do równoważnego automatu bez nich, podobnie jak w przypadku kompresji ruchów w DFA. Wydaje się, że taka konwersja nie jest tak trywialna jak w przypadku DFA i nie jestem pewien, czy to w ogóle możliwe. $\Gamma$ $\Gamma$ $\epsilon$ $\epsilon$

Czy zatem oba są równoważne pod względem mocy? Pytam tylko, ponieważ wszyscy wydają się zakładać, że DPDA mają ruchów i zastanawiam się, dlaczego takie założenie istnieje, ponieważ wydaje się, że jest to bardziej złożony model. $\epsilon$

automata-theory context-free Phylliida
źródło

W porządku. Czy jest więc powód, dla którego studiujemy tylko te z ruchami

ϵ

$\epsilon$

Phylliida,

Więc właśnie zdałem sobie sprawę, że faktycznie możesz rozpoznać

. Po prostu zaczynasz w stanie akceptacji, a następnie po przeczytaniu pierwszego

pchasz i na stos, a po przeczytaniu drugiego

wciskasz # na stos. Po tym, piszesz

do stosu dla każdego innego

można przeczytać, zaczynając od

można przeczytać po naciśnięciu # do stosu.

L = {a^{2 n} b^{n}}

$L=\{a^{2n}b^n\}$

a

$a$

a

$a$

a

$a$

a

$a$

a

$a$

Phylliida,

Następnie, jeśli czytasz

, wiedząc, że czytasz nieparzystą liczbę

, które odrzucasz (usiądź w zablokowanym stanie), w przeciwnym razie przejdziesz do innego stanu i zepchniesz

ze stosu. Powtórz to dla każdego przeczytanego

. Jeśli ostatecznie podczas analizowania

, # znajduje się na górze stosu zamiast

, wprowadź stan akceptacji. Następnie wprowadź stan odrzucenia, jeśli zostaną odczytane jakiekolwiek inne symbole. W każdym przypadku innym niż te opisane powyżej wprowadź stan odrzucenia. Czy to działa?

b

$b$

a

$a$

a

$a$

b

$b$

b

$b$

a

$a$

Phylliida,

Dla mnie brzmi dobrze.

Klaus Draeger,

Popraw mnie, jeśli się mylę, ale zgadzam się. Uważam też, że można rozpoznać

z DPDA że zawsze porusza się w prawo na taśmie wejściowej (nigdy zatrzymania). Jedyną trudną częścią jest doprowadzenie go do stanu końcowego. Akceptacja DPDA może być trudna.

{a^{2 n} b^{n}}

$\{ a^{2n}b^{n} \}$

Michael Wehar

Być może znalazłem kilka istotnych informacji w:

Jean-Michel Autebert, Jean Berstel, Luc Boasson; Języki bezkontekstowe i automaty pushdown; Podręcznik języków formalnych; 1997, s. 111–174

DPDA bez przejścia są znane jako deterministyczne automaty wypychające w czasie rzeczywistym . $\epsilon$

Na przykład są mniej wydajne niż DPDA

$L = \{ a^n b^p c a^n \mid p,n > 0\} \cup \{ a^nb^pdb^p\mid p,n > 0 \}$

jest deterministyczny i może być rozpoznany przez DPDA, ale nie może być rozpoznany przez żaden DPDA w czasie rzeczywistym .

Co możesz zrobić, to wyeliminować rosnące przejścia: $\epsilon$

Twierdzenie 5.4 : Dla każdego DPDA możliwe jest zbudowanie DPDA rozpoznającego ten sam język, tak że zmniejsza się dowolna reguła . $\epsilon$

Marzio De Biasi
źródło

Wielkie dzieki! To odpowiada pierwszej części mojego pytania. Druga część to - dlaczego ich nie studiujemy? Wydaje się, że wszyscy skupiają się na tych, które nie są wyświetlane w czasie rzeczywistym, co wydaje mi się dziwne.

Phylliida,

@DanielleEnsign: w Google można znaleźć wyniki dotyczące RDPDA, na przykład problem równoważności jest rozstrzygalny . Ale zgadzam się z tobą, nie przyciągnęły one zbyt wiele uwagi.

Marzio De Biasi,

Czy DPDA bez ruchów

Odpowiedzi: