Ich stecke in der folgenden Frage fest:
"Reguläre Sprachen sind genau diejenigen, die von endlichen Automaten akzeptiert werden. Zeigen Sie, dass, wenn die Sprache von einem endlichen Automaten akzeptiert wird, auch von einem endlichen akzeptiert wird; besteht aus allen Wörtern von umgekehrt. " L R L
Antworten:
Wenn wir also eine reguläre Sprache , wissen wir (im Wesentlichen per Definition), dass sie von einigen endlichen Automaten akzeptiert wird. Es gibt also eine endliche Menge von Zuständen mit geeigneten Übergängen, die uns genau dann vom Ausgangszustand in den akzeptierenden Zustand bringen, wenn die Eingabe erfolgt ist eine Zeichenkette in . Wir können sogar darauf bestehen, dass es nur einen akzeptierenden Staat gibt, um die Dinge zu vereinfachen. Um die Umkehrsprache zu akzeptieren, müssen wir nur die Richtung der Übergänge umkehren, den Startzustand in einen Akzeptanzzustand und den Akzeptanzzustand in den Startzustand ändern. Dann haben wir eine Maschine, die im Vergleich zum Original "rückwärts" ist und die Sprache akzeptiert .L L RL L LR
quelle
Sie müssen zeigen, dass Sie immer einen endlichen Automaten konstruieren können, der Zeichenfolgen in akzeptiert, vorausgesetzt, dass ein endlicher Automat Zeichenfolgen in akzeptiert . Hier ist ein Verfahren, um das zu tun.LR L
Lassen Sie uns das alles formalisieren. Wir beginnen mit dem Satz.
Satz. Wenn eine reguläre Sprache ist, ist es auch .L LR
Sei eine NFA und sei . Das unten definierte -NFA akzeptiert die Sprache .A = ( QEIN, ΣEIN, δEIN, qEIN, FEIN) L = L ( A ) ϵ EINR LR
Beweis. Zunächst wir beweisen die folgende Aussage: ein Pfad von zu in , markiert mit , wenn und nur wenn ein Pfad von zu in , markiert mit (die Umkehrung von ) für . Der Beweis erfolgt durch Induktion über die Länge von .∃ q p EIN w ∃ p q EINR wR w q,p∈QA w
Vermietung und für einige und Substituieren für gewährleistet , daß . Da es einen mit bezeichneten Pfad von zu jedem Zustand in (3. in der Definition von ) und einen mit bezeichneten Pfad von jedem Zustand in zu dem Zustand gibt, gibt es einen Pfad markiert mit von bis . Dies beweist den Satz.q=qA p=s s∈FA wR axR q∈δ∗AR(s,wR) ∀s∈FA ϵ qs FA AR FA qA wR ϵwR=wR qs qA
Beachten Sie, dass dies beweist, dass .(LR)R=L
Bitte bearbeiten Sie, wenn es irgendwelche Formatierungsfehler oder Fehler in meinem Proof gibt ....
quelle
Um die oben beschriebenen automatenbasierten Transformationen zu ergänzen, können Sie auch beweisen, dass reguläre Sprachen unter Umkehr geschlossen sind, indem Sie zeigen, wie ein regulärer Ausdruck für in einen regulären Ausdruck für konvertiert wird . Dazu definieren wir eine Funktion für reguläre Ausdrücke, die einen regulären Ausdruck für eine Sprache als Eingabe akzeptiert und dann einen regulären Ausdruck für die Sprache . Dies wird induktiv über die Struktur regulärer Ausdrücke definiert:L R R E V R L R ' L RL LR REV R L R′ LR
Sie können diese Konstruktion formal als Übung nachweisen.
Hoffe das hilft!
quelle
rev()
Notation. :) hab ich auch hingelegtREV(R1&R2) = REV(R1)&REV(R2)
; Ich habe eine Regex-Implementierung, die Schnittmenge hat. Ja; Ich denke über das Hinzufügen eines Operators für die Umkehrung möglicherweiseR\r
(umgekehrtes vorangehendes Regex-Element).REV(~R)
ist die Umkehrung der Menge aller Saiten außerhalb von R. Ist das dasselbe wie~REV(R)
: die Menge aller Saiten außerhalb der Umkehrung der mit R bezeichneten Menge? Dies ist überhaupt nicht klar, da alle Palindrome inR
auch in sindREV(R)
.Beweisen Sie mit regulären Ausdrücken, dass, wenn eine reguläre Sprache ist, die \ emph {Umkehrung} von , auch regulär ist. Insbesondere wird ein regulärer Ausdruck gegeben, der beschreibt , zeigen mit Induktion , wie sie in einem regulären Ausdruck umzuwandeln , die beschreibt . Ihr Beweis sollte nicht auf NFAs zurückgreifen. L L R = { w R : w ∈ L } L L RL L LR={wR:w∈L} L LR
Wir gehen davon aus, dass wir einen regulären Ausdruck erhalten, der beschreibt . Schauen wir uns zuerst den Concatination-Operator ( ) an und gehen wir dann zu fortgeschritteneren Operatoren über. Unsere Verkettungsfälle befassen sich also mit der Länge dessen, was verkettet wird. Also werden wir zuerst alle Verkettungen von nach aufbrechen . Wenn Sie sich mit diesen befassen, teilen Sie die Komponenten so weit wie möglich auf: , aber Sie können natürlich die assoziative Reihenfolge zwischen verschiedenen Auffassungen nicht aufbrechen.∘ a b a ∘ b ( a b ∪ a ) b → ( a b ∪ a ) ∘ bL ∘ ab a∘b (ab∪a)b→(ab∪a)∘b
Wenn∅R→∅
Wenn , haben wir die leere Zeichenkette, die bereits umgekehrt ist, so dass sich der Mechanismus nicht änderts=ϵ
Wenn nur ein Buchstabe ist, wie in , ist die Umkehrung nur dieser Buchstabe,s ∈ Σ ss s∈Σ s
Wenn , haben wir einen einzelnen Bestandteil, so dass wir diesen Bestandteil einfach umkehren und somitσ Rs=σ σR
Wenn wobei k ungerade ist, haben wir einen regulären Ausdruck, der geschrieben werden kann als . Die Umkehrung dieser Saiten mit gerader Länge ist einfach. Den 0-Index einfach mit dem k-Index tauschen. Dann wechseln Sie den 1-Index mit k-1-Index. Fahren Sie fort, bis jedes Element einmal geschaltet wurde. Somit ist das letzte Element jetzt das erste in der Reg-Ex und das erste ist das letzte. Der vorletzte ist der zweite und der zweite der vorletzte. Wir haben also eine umgekehrte Reg-Ex, die die umgekehrte Zeichenfolge akzeptiert (der erste Buchstabe ist der letzte usw.). Und natürlich kehren wir jeden Bestandteil um. So würden wir erhalten( σ 0 ∘ σ 1 . . . σ k - 1 ∘ σ k ) ( σ R ks=(σ0σ1...σk−1σk) (σ0∘σ1...σk−1∘σk) (σRkσRk−1...σR1σR0)
Wenn wobei k gerade ist, haben wir im Allgemeinen einen regulären Ausdruck, der geschrieben werden kann als . Die Umkehrung dieser Saiten mit gerader Länge ist einfach. Den 0-Index einfach mit dem k-Index tauschen. Dann wechseln Sie den 1-Index mit k-1-Index. Fahren Sie fort, bis jedes Element einmal gewechselt wurde, aber das k / 2-Element (eine ganze Zahl, weil k gerade ist). Somit ist das letzte Element jetzt das erste in der Reg-Ex, und das erste ist das letzte. Der vorletzte ist der zweite und der zweite der vorletzte. Wir haben also einen umgekehrten reg ex, der den umgekehrten String akzeptiert (der erste Buchstabe ist der letzte usw.). Und dieser mittlere Buchstabe. Und natürlich vertauschen wir jeden Bestandteil. So würden wir bekommen( σ 0 ∘ σ 1 . . . σ k - 1 ∘ σ k ) ( σ R k σ R k - 1 . . . σ R k / 2 . . .s=(σ0σ1...σk/2...σk−1σk) (σ0∘σ1...σk−1∘σk) (σRkσRk−1...σRk/2...σR1σR0)
Okay, der schwierige Teil ist erledigt. Schauen wir uns den Operator an. Dies ist nur eine Vereinigung von Mengen. So zwei Saiten gegeben, , die Umkehrung der nur . Die Gewerkschaft wird sich nicht ändern. Und das macht Sinn. Dies fügt einer Menge nur Zeichenfolgen hinzu. Es spielt keine Rolle, in welcher Reihenfolge sie zum Set hinzugefügt werden, alles, was zählt, ist, dass sie es sind.s 1 , s 2 s 1 ∪ s 2 s R 1 ∪ s R 2∪ s1,s2 s1∪s2 sR1∪sR2
Der kleene Sternoperator ist der selbe. Es fügt lediglich Strings zu einem Set hinzu und sagt uns nicht, wie wir das String-Persay aufbauen sollen. Also, um einen kleene Stern einer Zeichenfolge umzukehren , ist nur . Umkehrung kann nur durch sie bewegen.( ( s R ) ∗ )s ((sR)∗)
So umkehren diese wir einfach an die Regeln. Um die äußere Vereinigung umzukehren, kehren wir einfach die beiden Komponenten um. Um dies umzukehren: kleene star, wir kehren einfach um, was sich darin befindet . Um dann eine Verkettung umzukehren, indizieren wir und schalten dann am wenigsten um. Wir beginnen also mit und erhalten . Um diesen einzelnen Buchstaben umzukehren, erreichen wir unseren Basisfall und erhalten . Dieser oben beschriebene Prozess beschreibt eine induktive Beschreibung dieser Änderung. ( ( a ∪ b(((a∪b)∘(a))∗∪((a∪b)∘(b))∗)R ((a∪b)∘(a))∗ →(((a∪b)∘(a))R)∗ ( ( a ) R ∘ ( a ∪ b ) R ) ( a ) R → ( a )((a∪b)∘(a))R ((a)R∘(a∪b)R) (a)R→(a)
quelle