Welche Sprachklasse wird von Automaten mit endlichen Zuständen und

10

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,Σ,Δ,q0,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Σq0FΣε:=Σ{ε}

  • ΔQ×(Σε)k×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,(σ1,σ2,,σk),q)p(σ1,σ2,,σk)σiiε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.kk

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 .wkw

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 :

{anbnnN}
232-Kopf-NFA-Beispiel

(Hier bezeichnet eine mit gekennzeichnete Kante einen Übergang der Form .)σ1/σ2(p,(σ1,σ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

6005
quelle
2
Wenn ich mich ein wenig umsehe, sehe ich, dass in arxiv.org/abs/0906.3051 Mehrkopfautomaten erwähnt werden : Ihre Definition handelt von Zweiwegautomaten, aber sie definieren auch die Einwegvariante. Gibt es in diesem Artikel nicht etwas Hilfreiches? oder in seinen Referenzen, z. B. sciencedirect.com/science/article/pii/S0304397509006288
a3nm
2
Beachten Sie auch, dass sie Nicht-CF-Sprachen erkennen können: Ein 3-Kopf-DFA kann ; eine gute Referenzquelle: Markus Holzer und Martin Kutrib; Finite Automaten mit mehreren Köpfen: Charakterisierungen, Konzepte und offene Problemeanbncn#
Marzio De Biasi
2
Vielen Dank für die Referenzen in Papierform - dies war nur eine müßige Neugier und ich hatte die Literatur nicht überprüft. Wenn es sonst niemand tut, werde ich Literatur lesen und mit einer Antwort antworten, die die bekannten Ergebnisse zusammenfasst.
6005

Antworten:

5

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:

Wechsel

Probabilistische Berechnung

Probabilistische und Quantenberechnung

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

Abuzer Yakaryilmaz
quelle