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

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.

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.

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

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.