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?

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

Łatwo jest zdecydować za pomocą maszyny HAL - zauważ, że maszyna musi śledzić dwie właściwości: liczbę zer w x vs y i długość x , y (vs z ). Może wcisnąć a do stosu za każde zero, które widzi w x (a następnie wyskoczyć za dowolne zero widoczne w y ); dodatkowo wypycha dla dowolnego bitu w x , y (i później wyskakuje dla dowolnego bitu z ). 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, L = { z ⊥ y ⊥ x ∣ x , y , z ∈ { 0 , 1 } , # 0 ( x ) = # 0 ( y )  i  | x | + | y | = Oo } Pokażemy, że żadna maszyna HAL może zdecydować L .$L = L_{\times 2}^R$

Intuicja jest następująca. Jak wyżej, maszyna musi śledzić zarówno długość i liczbę zer w x , y . Jednak w tym przypadku należy je śledzić jednocześnie . Nie można tego zrobić za pomocą stosu. Bardziej szczegółowo, po odczytaniu z , sterta zawiera informacje o długości | x | + | y | . podczas odczytywania y maszyna musi także przechowywać w stercie liczbę zer w y . 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 x , 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ść 1 . 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 c (dla niektórych wystarczająco dużych stałych c ).$\varepsilon$$^1$$c$$c$

Dowód.
Załóżmy, że decyduje L , i rozważ wystarczająco długi sygnał wejściowy (powiedzmy, o długości 4 n , a więc | x | = | y | = n , | z | = 2 n , ignorując poniższe znaki ). Aby być konkretnym, popraw z , y i załóż, że # 0 ( y ) = n / 2 . Zauważ, że są ($H$$L$$4n$$|x|=|y|=n$$|z|=2n$$\bot$$z,y$$\#_0(y) = n/2$różnexjest taki, żez⊥Y⊥x∈L.${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 3 n c symboli (gdzie każdy symbol jest od stałej alfabetu y ) przez założeniem. Są jednak ($z\bot y$$3nc$$\Gamma$różnex's, 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ściowex1,x2,które powinny zostać zaakceptowane, aby:${n \choose n/2}$$x's$$x_1,x_2$

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

Oczywiste jest, że maszyna musi zaakceptować słowo , gdzie x p 1 jest prefiksem x długości n / 2, a x s 2 jest sufiksem x 2 o tej samej długości. Należy zauważyć, że liczba zer iN x p 1 x s 2 różni się od liczby jedynek w x 1 oraz x 2 (to znaczy, z # 0 ( $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 x 1 i x 2 , 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ć.} 2 ^{Naprawmy x 1, aby był prefiksem (o długości n / 2 miał dokładnie n / 4 zer). Przypomnijmy, że używającprzybliżenia Stirlingaznamy ten log ( n}$^1$
$^2$ ^{$x_1$$n/2$$n/4$gdzieH()jestfunkcją binarną entropii. PonieważH(1/4)≈0,81mamy ($\log {n \choose k} \approx nH(k/n)$$H()$$H(1/4) \approx 0.81$dla wystarczająco dużegon. ${n \choose n/4} > 2^{0.8n}$$n$}3^{Zakładając alfabetΓ, są| Γ| nróżnych łańcuchów o długościn, 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óżnychposortowanychciągów o rozmiarzenwynosi (n+1}
$^3$ ^{$\Gamma$$|\Gamma|^n$$n$$n$, dla stałej| Γ| .${n+1 \choose |\Gamma|-1}\approx n^{|\Gamma|}$$|\Gamma|$}