Wörter, die das gleiche rechts- und linksassoziative Produkt haben

Ich habe begonnen, nicht deterministische Automaten mit dem Buch von Hopcroft und Ullman zu studieren . Ich stecke in einem Problem fest, das ich sehr interessant fand:

Geben Sie einen nicht deterministischen endlichen Automaten an, der alle Zeichenfolgen akzeptiert, die denselben Wert haben, wenn sie von links nach rechts wie von rechts nach links ausgewertet werden, indem Sie gemäß der folgenden Tabelle multiplizieren:

$\qquad \displaystyle\begin{array}{c|ccc} \times & a & b & c \\ \hline a & a & a & c \\ b & c & a & b \\ c & b & c &a \end{array}$

Wenn wir also die Zeichenfolge , ist das Produkt von links nach rechts und das Produkt von rechts nach links ist( a × b ) × c = a × c = c a × ( b × c ) = a × b = $abc$
$(a \times b) \times c=a \times c=c$
$a \times (b \times c)=a \times b=a$

Daher sollte für die Automaten nicht akzeptabel sein. Für mich ist es offensichtlich, dass jede Zeichenfolge oder oder eine akzeptable Zeichenfolge ist (ihre rechte und linke Auswertung funktionieren mit denselben Teilzeichenfolgen). Es ist einfach, eine NFA anzugeben, die die Auswertung von links nach rechts beschreibt, aber das Problem ist, dass die Maschine, wenn sie versucht, die Auswertung von rechts nach links zu berechnen , meiner Meinung nach die Länge der Zeichenfolge kennen muss (daher ist unendlicher Speicher erforderlich).a a ∗ b b ∗ c c $abc$$aa^*$$bb^*$$cc^*$

Wie können also nicht deterministische Automaten von rechts nach links ausgewertet werden, um sie mit der Auswertung von links nach rechts zu vergleichen?

Der erste Trick besteht darin, sich die Multiplikationstabelle als Übergangstabelle eines Automaten vorzustellen, wobei jeder Zustand einen Buchstaben in Ihrer Multiplikationstabelle darstellt, sich aber noch keine Gedanken über die Akzeptanz macht. Die Buchstaben links und im Hauptteil der Tabelle sind also tatsächlich Zustände - es wäre genauer, sie als q a , q b , q c zu schreiben , aber ich werde es nicht tun. Die Buchstaben oben sind Eingaben.$A$$q_a, q_b, q_c$

Konstruieren Sie dann den Automaten (" T " für die Transponierung) für die umgekehrte Multiplikation durch Transponieren von A :$A_T$$T$$A$

$\qquad \displaystyle\begin{array}{c|ccc} A_T & a & b & c \\ \hline a & a & c & b \\ b & a & a & c \\ c & c & b & a \end{array}$

So führt in den Zustand c , und ebenfalls bewegt sich in den Zustand von , wie Sie beachten.$A(abc)$$c$a A $A_T(cba)$$a$$A_T$

geht jedoch davon aus , Sie von rechts nach links gehen, und wir möchten weiterhin von links nach rechts gehen. Der zweite Trick besteht also darin , den Automaten umzukehren (nicht die Multiplikation, die uns nur zurückbringen würde, wenn wir begonnen hätten), indem alle Pfeile umgekehrt werden, was zu einem nicht deterministischen Automaten , der in der folgenden Übergangstabelle angegeben ist. mit Teilmengen, die durch verkettete Buchstaben angezeigt werden, damit das Huhn nicht zerkratzt, so dass wirklich . (Ich hoffe, ich habe alles richtig gemacht - scheint zu funktionieren).A T R a c { a , c $A_T$$A_{TR}$$ac$$\{a,c\}$

$\qquad \displaystyle\begin{array}{c|ccc} A_{TR} & a & b & c \\ \hline a & ab & b & c \\ b & ∅ & c & a \\ c & c & a & b \\ \hline ab & ab & bc & ac \\ bc & c & ac & abc \\ ac & abc & ab & bc \\ abc & abc & abc & abc \\ ∅ & ∅ & ∅ & ∅ \end{array}$

Sie können dies als nicht deterministischen Automaten mit nur den drei Zeilen über der Zeile oder als bestimmte Version mit allen 8 Zeilen interpretieren.

Schließlich ist die Maschine das Problem zu lösen das Kreuzproduktautomaten der ursprünglichen und , das ist den Schnittverhalten der beiden Automaten auszuführen (wir nicht brauchen jede Mehr). hat Zustände, die Paare wie . Die Übergangsfunktion führt und unabhängig voneinander aus. Ein einzelner Startzustand geht in unter Eingabe , in unter Eingabe usw. A T R A × A T R A T A × A T R ⟨ a , a c ⟩ A A T R ⟨ 1 , 1 ⟩ ⟨ a , a ⟩ a ⟨ b , b ⟩ $A$$A_{TR}$$A \times A_{TR}$$A_T$$A \times A_{TR}$$\langle a,ac\rangle$$A$$A_{TR}$$\langle 1,1 \rangle$$\langle a,a \rangle$$a$$\langle b,b \rangle$$b$

Annahme von Zuständen in der nicht-deterministischen Version usw. In der deterministischen Version Annahme Zustände sind Paare , bei denen die erste Komponente ∈ des zweiten Komponentensatzes, wie ⟨ einen , ein ⟩ oder ⟨ b , b c ⟩ .$\langle a,a \rangle$$\in$$\langle a,a \rangle$$\langle b,bc \rangle$

, wie gezeigt vergrößert und bestimmt, hat 25 = 3 ⋅ 8 + 1 Zustände. Verzeihen Sie mir also, wenn ich es nicht im Detail schreibe. Die nicht deterministische Version hat jedoch nur 10 = 3 ⋅ 3 + 1 Zustände.$A \times A_{TR}$$25=3\cdot 8+1$$10=3\cdot 3+1$

Wenn L eine reguläre Sprache ist, ist L R , die Sprache, die aus derUmkehrungaller Wörter in L besteht , ebenfalls regulär. Nehmen Sie dies als Übung.$(\ast)$$L$$L^R$$L$

Wie hilft uns das, das Problem zu lösen? Sei die Sprache, die aus allen Zeichenfolgen besteht, die bei der Bewertung von links nach rechts a , b , c ergeben . Die Sprache, die Sie interessiert, ist ( L a ∩ L R a ) ∪ ( L b ∩ L R b ) ∪ ( L c ∩ L R c ) . Dies zeigt, dass, wenn Sie wissen, wie man beweist $L_a,L_b,L_c$$a,b,c$

Wenn Sie die Idee des Beweises von , können Sie wahrscheinlich einfach den Automaten konstruieren. Betrachten wir das also. Versuchen wir insbesondere, eine NFA für L R a zu erstellen , die Sprache aller Zeichenfolgen, die bei der Auswertung von rechts nach links zu a ausgewertet werden.$(\ast)$$L_a^R$$a$

Die Idee ist dies. Angenommen, der erste Buchstabe, den Sie sehen, ist . Dann muss der Rest der Zeichenfolge zu b ausgewertet werden (da b x = a x = b impliziert ). Ähnliches gilt, wenn der erste Buchstabe c ist . Wenn der erste Buchstabe a , jedoch kann der Rest entweder bewerten a oder b , oder null sein. Mit einer NFA können wir raten (und später unsere Vermutung überprüfen).$b$$b$$bx = a$$x = b$$c$$a$$a$$b$

Dieser Hinweis sollte Ihnen genug zum Nachdenken geben und hoffentlich das Problem lösen.

Süß.

Erstellen Sie zunächst einen Automaten, der das Produkt von links nach rechts berechnet. Einfach! Setzen Sie einen Übergang wann immerx⋅y=z. Es gibt drei Zustände{ → a , → b , → c },die die drei möglichen Produkte darstellen. Beginnen Sie in einem vierten Zustand → 1 mit → $\overrightarrow x \xrightarrow{\;y\;} \overrightarrow z$$x \cdot y = z$$\{\overrightarrow a,\overrightarrow b,\overrightarrow c\}$$\overrightarrow 1$ für allex. Der Endzustand istgenau dann → x, wenn das Produkt des Eingabeworts von links nach rechtsx ist.$\overrightarrow 1 \xrightarrow{\;x\;} \overrightarrow x$$x$$\overrightarrow x$$x$

Erstellen wir nun einen Automaten, der das Produkt von rechts nach links berechnet. Dieser wird nicht deterministisch sein. Wie machen wir das? Einfach… Um in die andere Richtung zu gehen, kehren Sie einfach alles um : die Pfeile und die Richtung des Produkts.

Wo wir vorher hatten $\overrightarrow{x} \xrightarrow{\;y\;} \overrightarrow{x \cdot y\:}$nehmen wir jetzt : Wenn wir das Wort von links nach rechts konsumieren, wechseln wir von einem Produkt zu seinem rechten Faktor. Oder mit anderen Worten: ← $\overleftarrow{x \cdot y\:} \xleftarrow{\;x\;} \overleftarrow{y}$$\overleftarrow{x} \xleftarrow{\;y\;} \overleftarrow{y \cdot x\:}$.

Fügen Sie einen getrennten Knoten um das leere Wort zu erhalten. Alle Knoten sind initial.$\overleftarrow 1$

$(\overrightarrow{x_1}, \overleftarrow{x_2}) \xrightarrow{\;y\;} (\overrightarrow{z_1}, \overleftarrow{z_2})$$\overrightarrow{x_1} \xrightarrow{\;y\;} \overrightarrow{z_1}$$\overleftarrow{x_2} \xrightarrow{\;y\;} \overleftarrow{z_2}$$(\overrightarrow 1, \overleftarrow x)$$(\overrightarrow x, \overleftarrow x)$$x$

Es scheint, dass Ihr Hauptproblem darin besteht, Nichtdeterminismus zu verwenden. Lassen Sie mich darauf näher eingehen.

Die Grundidee, die die anderen verwenden, ist, dass eine nicht deterministische Maschine das Endergebnis erraten kann .

$abc$

• $a$$a$$bc$$a$$b$
  • $a$$b$$b$
    • $b$$c$
  • $b$$b$$c$
    • $c$$c$
• $b$$a$
• $c$$a$$bc$$c$
  • $c$$b$$a$
    • $a$$c$

Wie Sie sehen können, kann die NFA jede mögliche Berechnung von unten nach oben erraten und überprüfen . Da die akzeptierte Sprache als der Satz von Zeichenfolgen definiert ist, der von mindestens einem Lauf akzeptiert wird , werden alle nicht akzeptierenden Läufe für die Eingabe ignoriert. Die NFA "rät immer richtig".

Jetzt fällt es dieser NFA leicht, sich bis zum Ende an ihre erste Wahl zu erinnern. Wenn es akzeptiert, kann es das gespeicherte Symbol mit dem parallel erhaltenen lr-Produkt (deterministisch) vergleichen (wie sich die Sprachschnittstelle auf NFA bezieht, wird sicherlich in Ullman / Hopcroft und jedem anderen grundlegenden Lehrbuch behandelt).