Potwierdzenie zamknięcia w zamian języków akceptowanych przez automaty min-heap

To jest kolejne pytanie tego .

W poprzednim pytaniu dotyczącym egzotycznych automatów stanowych Alex ten Brink i Raphael odnieśli się do możliwości obliczeniowych szczególnego rodzaju automatu stanowego: automatów typu min-heap. Udało im się wykazać, że zestaw języków akceptowanych przez takie maszyny ( ) nie jest ani podzbiorem, ani nadzbiorem zestawu języków bezkontekstowych. Biorąc pod uwagę skuteczne rozstrzygnięcie i pozorne zainteresowanie tym pytaniem, przystępuję do zadawania kolejnych pytań. $HAL$

Wiadomo, że zwykłe języki są zamknięte w ramach różnych operacji (możemy ograniczyć się do podstawowych operacji, takich jak zjednoczenie, przecięcie, uzupełnienie, różnica, konkatenacja, gwiazda Kleene i odwrócenie), podczas gdy języki bezkontekstowe mają inne zamknięcie właściwości (są zamknięte w związku zjednoczenia, konkatenacji, gwiazdy Kleene i odwrócenia).

Czy HAL jest zamknięty w trakcie cofania?

formal-languages automata closure-properties

— Patrick87
źródło

Jakie są zastosowania takich maszyn? Czy jest to ćwiczenie akademickie?

— Dave Clarke

@DaveClark Cóż, są to w większości ćwiczenia akademickie (o ile wiem, właśnie wymyśliłem je w powiązanym pytaniu). Mogą jednak wykonywać obliczenia w taki sam sposób, jak inne maszyny (DFA, TM itp.), Więc może być dla nich przydatne.

— Patrick87

To pytanie ilustruje, dlaczego chcesz, aby gramaty towarzyszyły twoim automatom. Arr, mój mózg!

— Raphael

Próbowałem to udowodnić, używając języka w formacie

, ale zajęło mi to zbyt wiele czasu i poddałem się. Może ten pomysł pomoże każdemu.

{x y ∣ y is a lexicographically sorted copy of x}

$\{xy \mid y\text{ is a lexicographically sorted copy of } x\}$

— Ran G.

@RanG .: Myślę, że to powinno działać. Z przyjemnością przyznam nagrodę za odpowiedź, która dowodzi, że język jest w

i daje uzasadnione uzasadnienie, że odwrócenie nie jest.

H A L

$\mathrm{HAL}$

— Raphael

Rozważmy język (gdzie oznacza liczbę zer w ).

L_{\times 2} = {x ⊥ y ⊥ z ∣ x, y, z \in {0, 1}, #_{0} (x) = #_{0} (y) and | x | + | y | = z}

$L_{\times 2} = \big\{ x\bot y\bot z \mid x,y,z\in \{0,1\}, \#_0(x)=\#_0(y) \text{ and } |x|+|y|=z\big \}$

#_{0} (x)

$\#_0(x)$

x

$x$

Łatwo jest zdecydować za pomocą maszyny HAL - zauważ, że maszyna musi śledzić dwie właściwości: liczbę zer w vs i długość (vs ). Może wcisnąć a do stosu za każde zero, które widzi w (a następnie wyskoczyć za dowolne zero widoczne w ); dodatkowo wypycha dla dowolnego bitu w (i później wyskakuje dla dowolnego bitu ). Ponieważ wszystkie s są zrzucane na stos, nie przeszkadzają w liczeniu. $L_{\times 2}$ $x$ $y$ $x,y$ $z$ 0 $x$ 0 $y$ 1 $x,y$ 1 $z$ 10 $\bot$ służy jako separator i można go praktycznie zignorować.

Teraz niech będzie językiem odwrotnym. To znaczy, Pokażemy, że żadna maszyna HAL może zdecydować . $L = L_{\times 2}^R$

L = {z ⊥ y ⊥ x ∣ x, y, z \in {0, 1}, #_{0} (x) = #_{0} (y) and | x | + | y | = z}

$L = \big\{z\bot y \bot x \mid x,y,z\in \{0,1\}, \#_0(x)=\#_0(y) \text{ and } |x|+|y|=z\big \}$

L

$L$

Intuicja jest następująca. Jak wyżej, maszyna musi śledzić zarówno długość i liczbę zer w . Jednak w tym przypadku należy je śledzić jednocześnie . Nie można tego zrobić za pomocą stosu. Bardziej szczegółowo, po odczytaniu , sterta zawiera informacje o długości . podczas odczytywania maszyna musi także przechowywać w stercie liczbę zer w . Jednak te informacje nie mogą zakłócać informacji, które sterty już mają na oczekiwanej długości $z$ $x,y$ $z$ $|x|+|y|$ $y$ $y$ $x$ być. Bardzo intuicyjnie albo informacja o liczbie zer będzie „poniżej” informacji o długości , a następnie nie będziemy mogli uzyskać do niej dostępu podczas czytania , lub będzie „powyżej” tej informacji, co spowoduje , że ta ostatnia będzie niedostępna, lub dwie informacje zostaną „zmieszane” i staną się bez znaczenia. $x$ $x$

Mówiąc bardziej formalnie, użyjemy pewnego rodzaju argumentu „pompowania”. Oznacza to, że weźmiemy bardzo długi sygnał wejściowy i pokażemy, że „stan” maszyny musi się powtórzyć podczas przetwarzania tego wejścia, co pozwoli nam „zastąpić” dane wejściowe, gdy maszyna powtórzy swój „stan”.

Dla formalnego dowodu wymagamy uproszczenia struktury maszyny HAL, a mianowicie, że nie zawiera ona „pętli” przejść . Przy takim założeniu widzimy, że dla każdego symbolu wejściowego przetwarzanego przez maszynę zawartość stosu może wzrosnąć / zmniejszyć o najwyżej (dla niektórych wystarczająco dużych stałych ). $\varepsilon$ $^1$ $c$ $c$

Dowód.
Załóżmy, że decyduje , i rozważ wystarczająco długi sygnał wejściowy (powiedzmy, o długości , a więc , , ignorując ). Aby być konkretnym, popraw i załóż, że . Zauważ, że są $H$ $L$ $4n$ $|x|=|y|=n$ $|z|=2n$ $\bot$ $z,y$ $\#_0(y) = n/2$ różnejest taki, że. ${n \choose n/2}$ $x$ $z\bot y \bot x \in L$

Rozważmy zawartość hałdy natychmiast po przetworzeniu . Zawiera on co najwyżej symboli (gdzie każdy symbol jest od stałej alfabetu ) przez założeniem. Są jednak $z\bot y$ $3nc$ $\Gamma$ różne, które powinny zostać zaakceptowana (która jest znacznie większa niż ilość różnych możliwych zawartości na stosie, ponieważ zwiększa się wykładniczo, podczas gdy inna ilość hałd wzrasta wielomianowo patrz poniżej). Weź dwa dane wejściowektóre powinny zostać zaakceptowane, aby: ${n \choose n/2}$ $x's$ $x_1,x_2$

Przedrostek długość o ma inną liczbę zer niż prefiksu w tej samej długości. $n/2$ $x_1$ $x_2$
Do czasu odczytania przez maszynę prefiksu o długości części , sterty wyglądają tak samo dla obu i , a także maszyna jest w tym samym stanie (musi się to zdarzyć dla niektórych , dla wystarczająco dużego , ponieważ istnieje więcej niż różnych opcji dla i co najwyżej $n/2$ $x$ $x_1$ $x_2$ $x_1,x_2$ $n$ $2^{0.8n}$ $^2$ $x_1,x_2$ różne opcje zawartości i stanu sterty ). $(3.5cn)^{|\Gamma|}|Q|$ $^3$

Oczywiste jest, że maszyna musi zaakceptować słowo , gdzie jest prefiksem długości a jest sufiksem o tej samej długości. Należy zauważyć, że liczba zer iN różni się od liczby jedynek w oraz (to znaczy, z $z\bot y \bot x_1^px_2^s$ $x_1^p$ $x$ $n/2$ $x_2^s$ $x_2$ $x_1^px_2^s$ $x_1$ $x_2$ ), ze względu na sposób, w jaki wybraliśmy i , doszliśmy do sprzeczności. $\#_0(y)$ $x_1$ $x_2$

^{Czy to założenie szkodzi ogólności?}^{Nie sądzę, ale to rzeczywiście wymaga dowodu.}^{Jeśli ktoś wie, jak obejść to dodatkowe założenie, chciałbym wiedzieć.}^Naprawmy^{aby był prefiksem (o długości}^{miał dokładnie}^zer).^{Przypomnijmy, że używając}^{przybliżenia Stirlinga}^{znamy ten} $^1$
$^2$ ^{$x_1$ $n/2$ $n/4$ gdziejestfunkcją binarną entropii. Ponieważmamy $\log {n \choose k} \approx nH(k/n)$ $H()$ $H(1/4) \approx 0.81$ dla wystarczająco dużego. ${n \choose n/4} > 2^{0.8n}$ $n$}^{Zakładając alfabet}^{, są}^{różnych łańcuchów o długości}^{, więc jeśli był to stos, to byliśmy przykręceni.}^{Jednak wypychanie „01” na stercie jest równoważne z wypychaniem „10” - na stercie przechowywana jest tylko posortowana wersja zawartości.}^{Liczba różnych}^{posortowanych}^{ciągów o rozmiarze}^wynosi
$^3$ ^{$\Gamma$ $|\Gamma|^n$ $n$ $n$ , dla stałej. ${n+1 \choose |\Gamma|-1}\approx n^{|\Gamma|}$ $|\Gamma|$}

— Ran G.
źródło

Ładny! Będę musiał przeczytać część formalną ponownie później. 1) Reklama ¹: patrz także tutaj . 2) Argument załamuje się, jeśli pozwalamy na niedeterministyczny wybór zwróconego symbolu sterty (spośród wszystkich symboli o tym samym priorytecie).

— Raphael