Z jaką klasą języków są rozpoznawane automaty skończone

DFA lub NFA odczytuje ciąg wejściowy z pojedynczą głowicą, przesuwając się od lewej do prawej. Naturalne wydaje się zastanawianie się nad maszynami o skończonym stanie, które mają wiele głowic , z których każda porusza się po wejściu od lewej do prawej, ale niekoniecznie w tym samym miejscu na wejściu, co inne.

Zdefiniujmy maszynę skończoną za pomocą $k$ głosi w następujący sposób:

K-head NFA jest krotką$(Q, \Sigma, \Delta, q_0, F)$, gdzie:

• Jak zwykle, $Q$ jest skończonym zbiorem stanów, $\Sigma$ jest skończonym alfabetem, $q_0$ jest stanem początkowym, oraz $F$jest zbiorem stanów akceptujących. Pozwolić$\Sigma_\varepsilon := \Sigma \cup \{\varepsilon\}$ oznacza zestaw znaków, w tym pusty ciąg znaków.

• $\Delta \subseteq Q \times (\Sigma_\varepsilon)^k \times Q$ to relacja przejścia: przejście $(p, (\sigma_1, \sigma_2, \ldots, \sigma_k), q)$ oznacza, że ​​jeśli maszyna jest w stanie $p$, może czytać $(\sigma_1, \sigma_2, \ldots, \sigma_k)$ takie, że $\sigma_i$ jest następną postacią dla głowy $i$ (lub $\varepsilon$ jeśli ta głowa się nie porusza), a następnie przejdź do stanu $q$.

Uruchomienie tego rodzaju maszyny (dowolna ścieżka zaczynająca się od stanu początkowego i kończąca się stanem akceptującym) powoduje nie jeden ciąg, ale $k$różne ciągi znaków (utworzone przez połączenie znaków podczas biegu). Następnie mówimy, że przebieg jest ważny, jeśli$k$ ciągi są identyczne.

Język maszyny jest zbiorem ciągów$w$ tak, że istnieje poprawny przebieg komputera, na którym $k$ ciągi utworzone wzdłuż tego przebiegu są równe $w$.

Pytanie: Jaką klasę języków rozpoznają takie maszyny? Czy zostało to zbadane?

Pierwszą obserwacją jest to, że takie maszyny produkują klasę większą niż zwykłe języki. Na przykład język

(Tutaj krawędź oznaczona $\sigma_1 / \sigma_2$ oznacza przejście formy $(p, (\sigma_1, \sigma_2), q)$.)

Drugim spostrzeżeniem jest jednak to, że nie wszystkie języki kontekstowe są rozpoznawane; na przykład wydaje się, że język Dyck nie jest przez nich rozpoznawany$k$-głowe maszyny.

Ten model jest jednym ze standardowych modeli w teorii automatów i został zbadany przez niektórych badaczy.

Odniesienia podane w pierwszym komentarzu są bardzo dobrym punktem wyjścia.

Gdy głowa jest dwukierunkowa, klasy języków rozpoznawane przez takie modele są identyczne z klasami przestrzeni logarytmicznej. Jednak gdy głowa jest jednokierunkowa, to według mojej wiedzy nie mamy podobnej dokładnej charakterystyki, ale mamy pewne nieporównywalne wyniki i pewne hierarchie oparte na liczbie głów.

Jeśli jesteś zainteresowany, polecam również sprawdzenie alternatywnych, probabilistycznych i kwantowych wersji automatów wielogłowicowych. Takie modele mogą być dość interesujące nawet przy użyciu pojedynczej głowicy, ponieważ obliczenia są podzielone na różne ścieżki, a następnie, na każdej ścieżce, głowa może uzyskać dostęp do innej części danych wejściowych.

Niektóre ogólne odniesienia:

• Maszyny Turinga z przestrzenią sublogarytmiczną - https://books.google.lv/books?id=vNPuNOo9BUYC

Alternacja

• Viliam Geffert - https://dblp.uni-trier.de/pers/hd/g/Geffert:Viliam

Obliczenia probabilistyczne

• Ioan I. Macarie - https://dblp.org/pers/hd/m/Macarie:Ioan_I=

Obliczenia probabilistyczne i kwantowe

• Rusins ​​Freivalds - https://dblp.uni-trier.de/pers/hd/f/Freivalds:Rusins
• Abuzer Yakaryilmaz - https://dblp.uni-trier.de/pers/hd/y/Yakaryilmaz:Abuzer

Powiązane modele: automaty licznikowe i automaty wykorzystujące kamyk.