Welche Sprachklasse wird von Automaten mit endlichen Zuständen und

Ein DFA oder NFA liest eine Eingabezeichenfolge mit einem einzelnen Kopf von links nach rechts durch. Es scheint natürlich, sich über Maschinen mit endlichen Zuständen zu wundern, die mehrere Köpfe haben , von denen sich jeder von links nach rechts durch die Eingabe bewegt, aber nicht unbedingt an derselben Stelle in der Eingabe wie die anderen.

Definieren wir eine endliche Zustandsmaschine mit Köpfen wie folgt:$k$

Ein k-Kopf-NFA ist ein Tupel , wobei:$(Q, \Sigma, \Delta, q_0, F)$

• Wie üblich ist eine endliche Menge von Zuständen, ist ein endliches Alphabet, ist ein Anfangszustand und ist eine Menge von Akzeptanzzuständen. Let den Satz von Zeichen einschließlich der leeren Zeichenfolge bezeichnen.$Q$$\Sigma$$q_0$$F$$\Sigma_\varepsilon := \Sigma \cup \{\varepsilon\}$

• $\Delta \subseteq Q \times (\Sigma_\varepsilon)^k \times Q$ ist die Übergangsrelation: Ein Übergang bedeutet, dass, wenn die Maschine sich im Zustand , kann er so , dass das nächste Zeichen für Kopf (oder wenn sich dieser Kopf nicht bewegt), und sich dann in den Zustand bewegen .$(p, (\sigma_1, \sigma_2, \ldots, \sigma_k), q)$$p$$(\sigma_1, \sigma_2, \ldots, \sigma_k)$$\sigma_i$$i$$\varepsilon$$q$

Ein Lauf dieser Art von Maschine (jeder Pfad, der vom Startzustand ausgeht und in einem akzeptierenden Zustand endet) führt nicht zu einer Zeichenfolge, sondern zu verschiedenen Zeichenfolgen (die durch Verketten der Zeichen entlang des Laufs gebildet werden). Dann sagen wir, dass der Lauf gültig ist , wenn die Zeichenfolgen identisch sind.$k$$k$

Die Sprache der Maschine ist der Satz von Zeichenfolgen so dass es einen gültigen Lauf der Maschine gibt, in dem die Zeichenfolgen, die entlang dieses Laufs erzeugt werden, alle gleich .$w$$k$$w$

Frage: Welche Sprachklasse wird von solchen Maschinen erkannt? Wurde es untersucht?

Eine erste Beobachtung ist, dass solche Maschinen eine Klasse produzieren, die größer ist als die regulären Sprachen. Zum Beispiel wird die Sprache von der folgenden Kopf-NFA mit Zuständen erkannt :

(Hier bezeichnet eine mit gekennzeichnete Kante einen Übergang der Form .)$\sigma_1 / \sigma_2$$(p, (\sigma_1, \sigma_2), q)$

Eine zweite Beobachtung ist jedoch, dass nicht alle kontextfreien Sprachen erkannt werden. Zum Beispiel scheint es, dass die Dyck-Sprache von diesen Kopf-Maschinen nicht erkannt werden kann.$k$

Dieses Modell ist eines der Standardmodelle in der Automatentheorie und wurde von einigen Forschern untersucht.

Die im ersten Kommentar angegebenen Referenzen sind sehr gute Ausgangspunkte.

Wenn der Kopf in beide Richtungen gerichtet ist, sind die von solchen Modellen erkannten Sprachklassen mit den logarithmischen Raumklassen identisch. Wenn der Kopf jedoch einseitig ist, haben wir meines Wissens keine ähnlich genaue Charakterisierung, aber wir haben bestimmte unvergleichliche Ergebnisse und einige Hierarchien, die auf der Anzahl der Köpfe basieren.

Wenn Sie interessiert sind, empfehle ich Ihnen, auch alternierende, probabilistische und Quantenversionen von Mehrkopfautomaten zu überprüfen. Solche Modelle können selbst bei Verwendung eines einzelnen Kopfes sehr interessant sein, da die Berechnung in verschiedene Pfade aufgeteilt ist und der Kopf dann in jedem Pfad auf verschiedene Teile der Eingaben zugreifen kann.

Einige allgemeine Referenzen:

• Turingmaschinen mit sublogarithmischem Raum - https://books.google.lv/books?id=vNPuNOo9BUYC

Wechsel

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

Probabilistische Berechnung

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

Probabilistische und Quantenberechnung

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

Verwandte Modelle: Multi-Counter-Automaten und Automaten mit Kieselsteinen.