NFA / DFA mit variablen Übergangsbedingungen

Question

Gute Nacht,

Nehmen wir an, ich habe eine Klasse, die implementiert eine NFA / DFA, deren Übergänge gespeichert werden in einer Struktur .NET Dictionary, und der ein eingegebenes Wort nimmt und erkennt eine Reihe von Wörtern in irgendeiner Weise von der Eingangs ableitbar. Außerdem nehmen wir an, dass der Automat eine generische Vorlage, die mit nur einer Wieder Kennzeichnung der Übergang Zeichen zu verschiedenen Wörtern der gleichen Länge angewendet werden kann. Was ist der beste Weg, um die Übergangsfunktion im Wörterbuch codieren, so dass sie die Übergänge neu etikettierte nach dem Zeichen des Eingangswortes zur Laufzeit sein können?

Vielen Dank.

Answer 1

Bitte beachten Sie die folgende Implementierung, die eine NFA und wandelt es in ein DFA nimmt (und dann in einem Diagramm) ein Wörterbuch verwenden, wie Sie sich:

NFA DFA

Ich bin nicht sicher, ob es die dynamische Relabeln Fähigkeit hat, die Sie suchen, aber es ist sehr gut (in-line) dokumentiert, so dass Sie viele Ideen, Ihnen zu helfen, mit Ihrem Projekt erhalten können.

Es gibt auch ein gutes (jüngeren) Artikel zum Thema Lambda-Übergänge, aber die Bild-Links des Artikels sind nicht mehr gültig. Allerdings kommt es mit herunterladbaren Quellcode FSAutomata.zip , dass Sie nach dem Lesen untersuchen der Artikel:

NFA mit Lambda Transition