Określanie możliwości min-stosu (lub innych egzotycznych) automatów stanowych

Zobacz koniec tego postu, aby uzyskać wyjaśnienie definicji automatów typu min-heap.

Można sobie wyobrazić użycie różnych struktur danych do przechowywania informacji do wykorzystania przez automaty stanów. Na przykład automatyczne automaty przechowują informacje na stosie, a maszyny Turinga używają taśmy. Automaty stanowe korzystające z kolejek oraz te, które używają dwóch wielu stosów lub taśm, zostały pokazane jako równoważne pod względem mocy maszynom Turinga.

Wyobraź sobie maszynę ze stertą min. Działa dokładnie tak, jak automat dociskający, z następującymi wyjątkami:

1. Zamiast patrzeć na ostatnią rzecz, którą dodałeś do sterty, możesz spojrzeć tylko na najmniejszy element (z kolejnością zdefiniowaną dla poszczególnych komputerów) aktualnie na sterty.
2. Zamiast usuwać ostatnią rzecz dodaną do stosu, możesz usunąć tylko jeden z najmniejszych elementów (z kolejnością zdefiniowaną dla poszczególnych komputerów) aktualnie na stercie.
3. Zamiast dodawać element na szczycie stosu, można jedynie dodać element do stosu, przy czym jego pozycja jest określana na podstawie innych elementów na stosie (z kolejnością zdefiniowaną dla poszczególnych komputerów).

Ta maszyna akceptuje wszystkie zwykłe języki, po prostu nie używając stosu. Może też przyjąć język $\displaystyle \{a^{n}b^{n} \in \{a, b\}^{*} \mid n \ge 0\}$ dodając 's do hałdy i usuwanie ' s ze sterty gdy czyta b „s. Może akceptować wiele innych języków bezkontekstowych. Nie może jednak zaakceptować na przykład { w ∈ { a , b } ∗ ∣ w = w R }$a$$a$$b$$\displaystyle \{w \in \{a, b\}^{*} \mid w = w^{R}\}$(podano bez dowodu). EDYCJA: czy może? Nie sądzę, żeby tak było, ale wcześniej byłem zaskoczony i jestem pewien, że będę zaskoczony, gdy moje założenia będą mnie nadal ... no cóż.

Czy może akceptować języki kontekstowe lub języki Turinga?

Mówiąc bardziej ogólnie, jakie badania, jeśli w ogóle, zostały przeprowadzone w tym kierunku? Jakie są ewentualne wyniki? Interesują mnie również inne odmiany egzotycznych automatów państwowych, być może te, które wykorzystują inne struktury danych do przechowywania lub różnego rodzaju ograniczenia dostępu (np. Jak LBA są ograniczonymi bazami TM). Referencje są mile widziane. Z góry przepraszam, jeśli to pytanie jest przejawem ignorancji.

Formalna definicja:

Podaję tutaj bardziej szczegółowe definicje automatów min-sterty w celu wyjaśnienia dalszej dyskusji w pytaniach dotyczących tego materiału.

Definiujemy automat niedeterministyczny typu 1 jako 7-krotny gdzie ...

1. jest skończonym, niepustym zestawem stanów;$Q$
2. jest stanem początkowym;$q_0 \in Q$
3. jest zbiorem stanów akceptujących;$A \subseteq Q$
4. jest skończonym, niepustym alfabetem wejściowym;$\Sigma$
5. jest skończonym, niepustym alfabetem wejściowym, gdzie waga symbolu γ ∈ Γ , w ( γ ) ∈ N jest taka, że w ( γ 1 ) = w ( γ 2$\Gamma$$\gamma \in \Gamma$$w(\gamma) \in \mathbb{N}$ ;$w(\gamma_1) = w(\gamma_2) \iff \gamma_1 = \gamma_2$
6. jest specjalnym symbolem z dołu stosu;$Z_0 \notin \Gamma$
7. jest funkcją przejścia.$\delta : Q \times (\Sigma \cup \{\epsilon\}) \times (\Gamma \cup \{Z_0\}) \rightarrow \mathcal{P}({Q \times \Gamma^*})$

Funkcja przejścia działa, zakładając początkowo pustą stertę składającą się tylko z . Funkcja przejściowy może dodać do sterty dowolnym Collection (skończoną, lecz może być pusty lub powtórzeń) elementów y 1 , γ 2 , . . . , γ k ∈ Γ . Alternatywnie, funkcja przejścia może usunąć wystąpienie elementu γ o najniższej masie w ( γ $Z_0$$\gamma_1, \gamma_2, ..., \gamma_k \in \Gamma$$\gamma$$w(\gamma)$wszystkich elementów pozostających na stercie (tj. element na stercie). Funkcja przejścia może wykorzystywać najwyższą (tj. Minimalną wagę) instancję symbolu do określania dowolnego przejścia.

Ponadto zdefiniuj deterministyczny automat na stosy typu 1 jako niedeterministyczny automat na stos typu 1, który spełnia następującą właściwość: dla wszystkich łańcuchów takich, że | x | = n i σ ∈ Σ , | δ n + 1 ( q 0 , x σ y , Z 0 ) | ≤ 1 .$x{\sigma}y \in \Sigma$$|x| = n$$\sigma \in \Sigma$$|\delta^{n+1}(q_0, x{\sigma}y, Z_0)| \leq 1$

Zdefiniuj również niedeterministyczny automat na stosy typu 2 dokładnie tak samo, jak niedeterministyczny automat na stos typu 1, z wyjątkiem następujących zmian:

1. jest skończonym, niepustym alfabetem wejściowym, w którym waga symbolu γ ∈ Γ , w ( γ ) ∈ N jest taka, że w ( γ 1 ) = w ( γ 2 ) niekoniecznie implikuje γ 1 = γ 2 ; innymi słowy, różne symbole sterty mogą mieć tę samą wagę.$\Gamma$$\gamma \in \Gamma$$w(\gamma) \in \mathbb{N}$$w(\gamma_1) = w(\gamma_2)$$\gamma_1 = \gamma_2$
2. Gdy instancje odrębnych symboli stosu o tej samej wadze są dodawane do stosu, ich względna kolejność jest zachowywana zgodnie z kolejnością stosu ostatnie wejście, pierwsze wyjście (LIFO).

Dzięki Raphael za wskazanie tej bardziej naturalnej definicji, która przechwytuje (i rozszerza) języki bezkontekstowe.

Dotychczasowe wyniki niektórych badań:

1. Automaty min-sterty typu 1 rozpoznają zestaw języków, który nie jest ani podzbiorem, ani nadzbiorem języków bezkontekstowych. [ 1 , 2 ]
2. Automaty min-sterty typu 2, z definicji, rozpoznają zestaw języków, który jest właściwym nadzbiorem języków bezkontekstowych, a także odpowiedni nadzór języków akceptowanych przez automaty typu min-sterty.
3. Języki akceptowane przez automaty min-stosu typu 1 wydają się być zamknięte pod zjednoczeniem, konkatenacją i gwiazdą Kleene, ale nie pod uzupełnieniem [ 1 ], przecięciem lub różnicą;
4. Języki akceptowane przez niedeterministyczne automaty stosu min 1 typu wydają się być odpowiednim nadzorem języków akceptowanych przez deterministyczne automaty determinacji typu 1.

Może brakować kilku innych wyników. Więcej wyników jest (prawdopodobnie) w drodze.

Dalsze pytania

1. Zamknięcie w trakcie cofania? -- Otwarty
2. Zamknięcie w ramach uzupełnienia? - Nie!
3. Czy niedeterminizm zwiększa siłę? -- Tak?
4. Czy dla typu 2? $HAL \subsetneq CSL$-- Otwarty
5. Czy dodawanie hałd zwiększa moc dla typu 1? - dla k > 2 (?)$HAL^1 \subsetneq HAL^2 = HAL^k$$k > 2$
6. Czy dodanie stosu zwiększa moc dla typu 1? -- Otwarty

Możesz rozpoznać kanoniczny język bezkontekstowy (ale kontekstowy) z tego typu automatem stanowym. Istotą jest to, że dodać tokeny do sterty dla każdej z postaci, a podczas analizowania b znaków, należy dodać „większych” żetony na stercie, więc tylko skończyć na dnie stosu, gdy masz analizowany wszystkie b postacie.$\{ a^n b^n c^n\ |\ n \geq 1 \}$$a$$b$$b$

Symbole Sterty są i b , gdzie < b . Konsumujemy wszystkich do symboli na wejściu i dodać do symboli na stercie. Jeśli napotkamy b , zmieniamy strategie: za każde b, które napotkamy, usuwamy a ze sterty i dodajemy b do sterty. Kiedy spotykamy c powinniśmy zabraknie ciągu s usunąć, a następnie dla każdego C w pozostałym wejście my usunięcia b$a$$b$$a < b$$a$$a$$b$$b$$a$$b$$c$$a$$c$$b$ze stosu. Jeśli sterty są puste na końcu, łańcuch jest w języku. Oczywiście odrzucamy, jeśli coś pójdzie nie tak.

Aktualizacja:

Język nie może być rozpoznany przez MIN sterty automatów. Załóżmy, że mamy do automatu min sterty, rozpoznaje E P A L . Patrzymy na „stan”, w którym znajduje się automat po odczytaniu w (pierwsza część wejścia, więc w R jest następne). Jedynym stanem, jaki mamy, jest zawartość sterty i konkretny stan automatu, w którym się znajduje. Oznacza to, że po rozpoznaniu $EPAL = \{ ww^R | w \in \{a, b\}^* \}$$EPAL$$w$$w^R$$w$, Wymaga to „państwo”, aby utrzymać wystarczająco dużo informacji, aby dopasować .$w^R$

W szczególności, aby to zrobić, muszą istnieć możliwych różnych stanów (gdzie n = | w | ), ponieważ istnieją 2 n możliwych słów składających się ze znaków a i b . Ponieważ istnieje tylko skończona liczba stanów i tylko skończona liczba znaków stosu, oznacza to, że istnieje pewne słowo w, dla którego stos zawiera wykładniczą liczbę niektórych znaków stosu, powiedzmy x .$2^n$$n = |w|$$2^n$$a$$b$$w$$x$

Najpierw dowodzimy twierdzenia o deterministycznych automatach na stosie min, a następnie rozszerzamy ten dowód na niedeterministyczne automaty na stosie minowym. W szczególności deterministyczne automaty, które rozpoznają jakiś język, nie znajdą się w nieskończonej pętli, co jest przydatną właściwością.

Udowodnimy, że sterty mogą zawierać maksymalnie najwyżej liczbę tokenów sterty, która jest liniowa pod względem liczby znaków odczytanych z danych wejściowych. To natychmiast wyklucza, że pojawia się wykładniczo wiele razy na stercie, co uzupełnia dowód, że E P A L nie może być rozpoznany przez automaty min-sterty.$x$$EPAL$

Ponieważ w naszym automacie mamy tylko skończoną liczbę stanów i ponieważ automat deterministyczny nie zapuści się w nieskończoną pętlę, po odczytaniu sygnału wejściowego doda do stosu co najwyżej stałą liczbę znaków stosu. Podobnie, zużywając jakiś symbol sterty , może dodać tylko co najwyżej stałą liczbę znaków sterty, które są ściśle większe niż y, i może jedynie zmniejszyć liczbę symboli y na stosie (w przeciwnym razie otrzymamy nieskończoną pętlę).$y$$y$$y$

Zużycie symboli sterty może zatem spowodować (ogromne) nagromadzenie większych symboli sterty, ale ponieważ istnieje tylko stała liczba różnych typów symboli sterty, jest to tylko stała liczba, niezależna od . Oznacza to, że liczba symboli sterty jest co najwyżej (duża) stała razy większa niż liczba symboli wejściowych odczytanych do tej pory. To uzupełnia dowód na przypadek deterministyczny.$n$

W przypadku niedeterministycznym dowód jest podobny, ale nieco trudniejszy: zamiast dodawać co najwyżej pewną stałą liczbę tokenów sterty, dodaje do sterty dowolną liczbę tokenów sterty. Najważniejsze jest jednak to, że liczba ta nie zależy od . W szczególności, jeśli możemy niedeterministycznie uzyskać dokładnie odpowiednie symbole sterty na stercie po rozpoznaniu w (odpowiednie do rozpoznania w R ), możemy również niedeterministycznie wybrać symbole sterty, które pasują do jakiegoś innego słowa w ' , a tym samym rozpoznać w w ′ R , co zaprzecza, że ​​automat minipapier rozpoznaje dokładnie E P $n$$w$$w^R$$w'$$w w'^R$ .$EPAL$

Aktualizacja 3: Zrobię ostry ostatni argument (o niedeterministyce). Zgodnie z powyższym argumentem musi istnieć nieskończony zestaw słów taki, że dla każdego w ∈ W , po rozpoznaniu w , sterta zawiera elementy ω ( | w | ) (zauważ, że możemy mówić o O ( f ( | w | ) $W \subseteq \{a,b\}^*$$w \in W$$w$$\omega(|w|)$$O(f(|w|))$ponieważ mamy nieskończony zestaw słów). Ponieważ nie możemy uzyskać tak wielu elementów na stercie za pomocą środków deterministycznych, musieliśmy mieć jakąś formę pętli, w której najpierw niedeterministycznie zdecydowaliśmy się dodać więcej elementów do stosu (bez zużywania danych wejściowych), a później postanowiliśmy wyjść z tego i musieliśmy przemierzać tę pętlę razy.$\omega(1)$

Weźmy zbiór wszystkich takich pętli używanych przez . Ponieważ istnieją tylko stany O ( 1 ) , rozmiar tego zestawu wynosi O ( 1 ) , a zestaw wszystkich jego podzbiorów to także O ( 1 ) . Zauważ teraz, że „deterministyczna” część ścieżek wykonania może przyczyniać się tylko do O ( | w | ) tokenów, co oznacza, że ​​wiele wykładniczej liczby różnych słów musi mieć ścieżki wykonania, których „deterministyczne” części przyczyniają się do tego samego tokeny do sterty. W szczególności jedynym sposobem na zdobycie większej liczby tokenów jest skorzystanie z pętli, które zidentyfikowaliśmy powyżej.$W$$O(1)$$O(1)$$O(1)$$O(|w|)$

Łącząc te obserwacje, oznacza to, że muszą występować dwa odrębne słowa w słowach , w 1 i w 2 , których „deterministyczna” część ścieżek wykonania wnosi te same tokeny do stosu, i które są zróżnicowane poprzez przyjęcie pewnego podzbioru pętle powyżej innej liczby razy, ale używają tego samego podzbioru pętli (pamiętaj, że jest tylko O ( 1 ) tych pętli).$W$$w_1$$w_2$$O(1)$

Możemy teraz pokazać, że może być również rozpoznany przez automat min-stosu: podążamy ścieżką wykonania dla w 1 jak wyżej, ale przemierzamy pętle tyle razy, ile razy ścieżka wykonania dla w 2 przemierza je. To wypełnia minimalną stertę tokenami, tak że w 2 jest akceptowane jako sufiks, tym samym uzupełniając dowód.$w_1 w_2$$w_1$$w_2$$w_2$

Aktualizacja 2:

Właśnie przyszło mi do głowy, że powyższe oznacza, że ​​możemy symulować deterministyczny automat min-sterty przy użyciu tylko przestrzeni logarytmicznej: przechowujemy licznik dla każdego typu postaci w min-sterty. Jak pokazano powyżej, tym licznikiem będzie co najwyżej , a zatem może być przechowywany przy użyciu tylko przestrzeni O ( log n ) (ponieważ istnieje tylko stała liczba tych liczników). To daje nam:$O(n)$$O(\log n)$

$\mathrm{DHAL} \subset \mathrm{L}$

$\mathrm{HAL} \subset \mathrm{NL}$

gdzie jest zbiorem języków rozpoznawanych przez jakiś deterministyczny automat min-hałdy.$\mathrm{DHAL}$

Oto, co (jak sądzimy) wiemy:

• (typ 1, typ 2)$\mathrm{HAL} \setminus \mathrm{CFL} \neq \emptyset$
• (typ 1)$\mathrm{CFL} \setminus \mathrm{HAL} \neq \emptyset$
• (typ 2, z definicji)$\mathrm{CFL} \subseteq \mathrm{HAL}$
• (typ 1, typ 2)$\mathrm{CSL} \setminus \mathrm{HAL} \neq \emptyset$

Zobacz szczegóły i kilka innych uwag poniżej.

$\mathrm{HAL} \setminus \mathrm{CFL} \neq \emptyset$

Ta część odpowiedzi dotyczy zarówno typu 1, jak i typu 2.

-Min sterty automatem (HA) ze skończoną uporządkowany sterty alfabetu przyjmuje .$L = \{ a^nb^nc^n \mid n \in \mathbb{N} \} \in \mathrm{CSL} \setminus \mathrm{CFL}$

Założenia: Podobnie do PDA, nasza funkcja przejścia zużywa najwyższy symbol sterty i zapisuje dowolną liczbę symboli sterty. Sterty początkowo zawierają wyróżniający się symbol który jest większy niż wszystkie inne symbole sterty.$\$$

Niech automat ze stertą min$A = (Q,\Sigma_I, \Sigma_H, \rightarrow, q_0, Q_F)$

• zbiór stanów$Q = \{q_0, q_1, q_2, q_f\}$
• wprowadzony alfabet.$\Sigma_I = \{a,b,c\}$
• alfabet sterty z zamówieniem a < b < $ .$\Sigma_H = {a,b,\$}$$a \lt b \lt \$$
• $Q_F = \{q_f\}$
• pomocą $\rightarrow\ \subseteq (Q \times \Sigma_I \times \Sigma_H) \times (Q \times \Sigma_H^*)$
  • dla wszystkich σ ∈ Σ $(q_0,a,\sigma) \rightarrow (q_0, a\sigma)$$\sigma \in \Sigma_H$
  • $(q_0,b,a) \rightarrow (q_1,b)$
  • $(q_1,b,a) \rightarrow (q_1,b)$
  • $(q_1,c,b) \rightarrow (q_2,\varepsilon)$
  • $(q_2,c,b) \rightarrow (q_2, \varepsilon)$
  • $(q_2,c,\$) \rightarrow (q_f, \varepsilon)$

Automat pisze jeden na stercie dla każdego A na wejściu. Kiedy pojawia się b , zużywa tyle b, ile było a , zapisując b na stosie dla każdego znalezionego b . To nie przeszkadza, ponieważ liczenie sterty wygodnie trzyma na górze. Dopiero po wszystkim są pobierane z hałdy są c akceptowane; dopiero po znalezieniu liczby c jako b (i tym samym jako a ) A przyjmuje pustą stertę i stan końcowy.$a$$a$$b$$b$$a$$b$$b$$a$$a$$c$$c$$b$$a$$A$

Dlatego też, .$\cal{L}(A) = L$

$\mathrm{CFL} \setminus \mathrm{HAL} \neq \emptyset$

Ta część odpowiedzi dotyczy tylko typu 1.

$\mathrm{EPAL} = \{ww^R \mid w \in \{a,b\}\}$$A$$\cal{L}(A) = L$

$w_1, w_2 \in \{a,b\}^*$$w_1 \neq w_2$$|w_1| = |w_2|$$A$$w_1$$w_2$$A$$w_1w_1^R$$w_2w_2^R$$w_1w_2^R \notin \mathrm{EPAL}$$w_2w_1^R$$\cal{L}(A) = \mathrm{EPAL}$

$\mathrm{CSL} \setminus \mathrm{HAL} \neq \emptyset$

Ta część odpowiedzi dotyczy zarówno typu 1, jak i typu 2.

$\mathrm{EPAL}$$\{ww \mid w \in \{a,b\}^*\}$$\mathrm{HAL}$

$\mathrm{HAL} \overset{?}{\subseteq} \mathrm{CSL}$

Jest to nadal otwarte zarówno dla typu 1, jak i typu 2.

Kolejne faktoidy

HA wydaje się być ortogonalna wobec podzbioru języków wrażliwych na kontekst, akceptowanych przez wbudowane automaty wypychające : Chociaż HA może symulować ograniczoną liczbę stosów, nie mogą symulować dowolnie wielu (jak potrafi EPA). HA może jednak uzyskać dostęp do najwyższych symboli stosów, które obecnie nie znajdują się na wierzchu (czego EPA nie może).