Jak udowodnić, że pętle ε nie są konieczne w urządzeniach PDA?

W kontekście naszego dochodzenia w sprawie automatów sterty chciałbym udowodnić, że dany wariant nie akceptuje języków niewrażliwych na kontekst. Ponieważ nie mamy równoważnego modelu gramatycznego, potrzebuję dowodu, który wykorzystuje tylko automaty; dlatego muszę pokazać, że automaty sterty mogą być symulowane przez LBA (lub równoważny model).

Oczekuję, że dowód zadziała podobnie do pokazania, że automaty wypychające akceptują podzbiór języków kontekstowych. Jednak wszystkie dowody, które znam, działają

używając gramatyki - tutaj fakt jest z definicji oczywisty - lub
są nieprzekonująco niejasne (np. tutaj ).

Mój problem polega na tym, że PDA (odpowiednio HA) może zawierać cykle -transitions, które mogą zapisywać symbole na stosie (odpowiednio stos). LBA nie może symulować dowolnych iteracji takich pętli. Wiemy o tym z hierarchii Chomsky'ego uzyskanej za pomocą gramatyki $\varepsilon$

każdy język bezkontekstowy ma -cycle-PDA lub $\varepsilon$
symulowanie LBA może zbyt często zapobiegać iteracji motocykli. $\varepsilon$

Intuicyjnie jest to jasne: takie cykle zapisują symbole niezależnie od danych wejściowych, dlatego zawartość stosu (stosu) przechowuje tylko pewną ilość informacji liniowo na całej długości cyklu (na razie pomijając nakładające się cykle). Nie możesz też pozbyć się tych rzeczy (jeśli musisz) inaczej niż używając innego -cycle. Zasadniczo takie cykle nie przyczyniają się do radzenia sobie z danymi wejściowymi, jeśli są powtarzane wielokrotnie, więc nie są konieczne. $\varepsilon$

Jak sformułować ten argument rygorystycznie / formalnie, zwłaszcza biorąc pod uwagę nakładanie się motocykli ? $\varepsilon$

automata pushdown-automata

— Raphael
źródło

Nie wiem, dlaczego twierdzisz, że motocykle mają ograniczoną długość, w przypadku niedeterministycznych palmtopów na pewno możliwe jest posiadanie nieskończonego cyklu, z którego automat może się wybić. Czy też nie rozumiem czegoś fundamentalnego?

ϵ

$\epsilon$

— vonbrand

Oczywiste jest, że mogą je mieć, ale włączenie CFL do CSL nie może być „konieczne”.

— Raphael

problem polega na tym, że zarys dowodu stwierdza, że nie istnieją.

— vonbrand,

Ran odpowiedź tutaj wydaje się istotne; bezpośrednio pokazuje, że istnieje palmtop bez -transitions. W końcu jednak potrzebuje gramatyki, więc technika nie przenosi się na automaty sterty.

ε

$\varepsilon$

— Raphael

W tej chwili jest to tylko niejasny pomysł, ale czy nie możesz użyć niedeterministycznego LBA i użyć niedeterminizmu, aby przerwać cykl na właściwym etapie (w taki sam sposób jak PDA)?

— Luke Mathieson

$\varepsilon$

$M$ $\mathcal{C}$ $\varepsilon$ $M$ $M$

$k$ $\mathbb{B}^{(k)} \in \mathcal{C}$ $\mathbb{B}$

Dowód jest długi i techniczny; dowody lematów 8 i 10 (odpowiednio 7.6 i 7.9) zawierają odpowiednie konstrukcje. Należy zauważyć, że podczas gdy oni nie używają modeli gramatycznych (wymagane w pytaniu) oni zrobić użycie walencyjnych przetworników .

Ciche przejścia w automatach z pamięcią G. Zetzsche (2013) [bardziej rozbudowany preprint na arXiv ]

— Raphael
źródło

FWIW, wyniki te nie wydają się przenosić na automaty sterty, ponieważ ich mechanizm przechowywania nie odpowiada monoidowi, a przynajmniej nie formom badanym przez Zetzschego.

— Raphael