Die Bedeutung der Zustandskomplexität in Automaten und regulären Sprachen?

14

Ich lese " Verkettung regulärer Sprachen und Beschreibungskomplexität " von Galina Jiraskova, 2009, über die Zustandskomplexität infolge der Verkettung zweier regulärer Sprachen (von Galina Jiraskova), kann aber die praktischen Auswirkungen der Zustandskomplexität nicht verstehen . Der erste triviale Gedanke, der mir auffiel, war, dass eine höhere Komplexität mehr Zeit und Platz für die Maschine erfordern würde. Ist das richtig? Gibt es auch andere Orte, an denen die Komplexität des Staates von Bedeutung und von Bedeutung ist?

Bearbeiten: Die Zustandskomplexität einer regulären Sprache ist die kleinste Anzahl von Zuständen in einem deterministischen endlichen Automaten (dfa), der die Sprache akzeptiert. Die nicht deterministische Zustandskomplexität einer regulären Sprache ist definiert als die kleinste Anzahl von Zuständen in einem nicht deterministischen endlichen Automaten (nfa) für die Sprache.

Airmine
quelle
Sichere Sache. Hat die Frage bearbeitet!
Airmine
Es scheint möglich, dass die Zeitung, die Sie gerade lesen, die Frage zu einem gewissen Grad beantwortet ...? Können Sie es genauer zitieren, z. B. den Titel und vorzugsweise einen Link zum PDF, falls verfügbar? Die Komplexität des FSM-Zustands zeigt sich in vielen Anwendungen und hat auch theoretische Auswirkungen ...
vzn
Ja, ich habe das Papier durchgesehen und die Referenzen durchgesehen. Konnte nicht viel im Zusammenhang mit den Anwendungen der staatlichen Komplexität finden.
Airmine
3
Nahezu jede FSM-Anwendung (von denen es viele gibt) muss die Zustandskomplexität für nichttriviale, "große" Probleme berücksichtigen. Beispiel. FSMs werden bei der Spracherkennung verwendet, wenn die Zustände Phoneme sind. Dies kann zu großen FSMs führen. FSMs werden auch häufig in EE-Anwendungen, z. B. Schaltungen usw., verwendet. Dort ist ein FSM mit hoher Komplexität eine "große" Schaltung. aber das Papier in Frage sucht sich vor allem auf der theoretischen Komplexität des Problems , wo obere / untere Schranken für „blowup“ oder „effiziente Minimierung“ (Kompression) sind Schlüsseleigenschaften zu studieren ....
VZN
Nicht gerade "praktisch", aber die Komplexität von Zuständen spielt eine Rolle bei der diversitätsbasierten Folgerung endlicher Automaten von Rivest und Schapire: [Konferenz ; Zeitschrift ].
Neal Young

Antworten:

18

Bei der Zustandskomplexität geht es wirklich um die präzise Beschreibung eines Objekts (in diesem Fall einer regulären Sprache), nicht um die Komplexität von Berechnungen. Das allgemeine Thema wird in der Literatur als "beschreibende Komplexität" bezeichnet und lehnt sich zum Teil an die klassische Arbeit von Meyer und Fischer von 1971 mit dem Titel "Ökonomie des Ausdrucks durch Automaten, Grammatiken und formale Systeme" an (siehe http: // people .csail.mit.edu / meyer / economy-of-description.pdf ). Dies ist nach wie vor ein aktiver Bereich mit einer jährlichen Konferenz (DCFS - Descriptional Complexity of Formal Systems).

Was Anwendungen betrifft, ist es an jedem Ort, an dem sich Ihr Programm im Wesentlichen auf eine endliche Maschine (z. B. Parser) stützt, gut, diese endliche Maschine so klein wie möglich zu halten.

Jeffrey Shallit
quelle
2
Oh ok. Eine Reduzierung der staatlichen Komplexität hilft also, eine bestimmte Sprache nur minimal darzustellen, anstatt sie einfacher zu verarbeiten?
Airmine
Da die meisten Algorithmen für Automaten direkt von der Zustandskomplexität abhängen, wird die Minimierung von Zuständen häufig mit dem Hintergedanken der Minimierung der Rechenkomplexität durchgeführt.
Denis
9

Lassen Sie mich ein konkretes Beispiel zur hervorragenden Antwort von Jeffrey Shallit hinzufügen.

Angenommen, Sie möchten ein Scrabble-Wörterbuch erstellen. Sie haben verschiedene Möglichkeiten, Ihr Wörterbuch darzustellen, z. B. eine Liste von Wörtern, Versuchen (Buchstabenbäume) oder deterministische Automaten. Gemäß [1] führt die Minimierung eines Versuchs auf einen Tagesanbruch [= DFA] zu einer erstaunlichen Platzersparnis. Die Anzahl der Knoten wurde von 117.150 auf 19.853 reduziert. Das als Rohwortliste dargestellte Lexikon benötigt ungefähr 780 KByte, während unser Dawg in 175 KByte dargestellt werden kann.

Wie Sie sehen, ist in diesem Fall die Komplexität des Zustands von entscheidender Bedeutung, insbesondere, wenn Sie ein effizientes Programm schreiben möchten, wie es die Autoren getan haben.

[1] Appel und Jacobson, das weltweit schnellste Scrabble-Programm , Communications of the ACM 31 , 572-578 (1988).

J.-E. Stift
quelle
4

Der Beweis, dass es entscheidbar ist, ob eine beliebige deterministische kontextfreie Grammatik (oder äquivalent ein deterministischer Pushdown-Automat) einen äquivalenten Zustandsautomaten hat, der dieselbe Sprache beschreibt, ist im Wesentlichen ein Beweis für die Zustandskomplexität endlicher Automaten, die deterministische kontextfreie Sprachen beschreiben: Die Größenbeschränkung dieser endlichen Automaten in Bezug auf die deterministischen Automaten gibt Grenzen für die Länge des Entscheidungsverfahrens.

Einzelheiten finden Sie unter " Regelmäßigkeit und verwandte Probleme für deterministische Pushdown-Automaten " von Leslie G. Valiant.

Alex ten Brink
quelle