Müssen Reguläre Ausdrücke für Endliche Automaten: gerade Anzahl von 1en und Auch die Anzahl der 0EN

Wie schreibt regulären Ausdruck für einen DFA mit Arden-theorem

Können statt Sprache, Symbole 0,1 wir nehmen Σ = {a, b} und folgenden neuen DFA.

Bemerken, Startzustand ist Q₀

Haben Sie nicht, aber In meiner Antwort Startzustand ist Q₀, Wo die endgültigen Zustand ist auch Q₀.

Sprache akzeptiert, ist die DFA ist die Menge aller strings bestehen aus symbol a und b, wo die Anzahl der symbol a und b sind sogar (einschließlich Λ).

Einige Beispiel-strings sind {Λ, aa, bb, abba, babbab } gibt es keine Einschränkung von Ordnung und prasseln der Erscheinung des symbols nur den beiden sollte auch die Anzahl der Zeit.

Hinweis: Λ ist zulässig, da Anzahl(a) und Anzahl(b) gleich null ist, ist auch.

Als ich sagte in meinem gefüttert Antwort: Wie schreibt regulären Ausdruck für eine DFA jeder Staat speichert einige Informationen. Unten ist eine, welche Informationen gespeichert werden, die in jedem Staat in den oben DFA.

Q₀: Sogar die Anzahl der a und auch die Anzahl der b

Q₁: Ungerade Anzahl von a und auch die Anzahl der b

F₂: Ungerade Anzahl von a und ungerade Anzahl von b

Q₃: Sogar die Anzahl der a und ungerade Anzahl von b

(Sie machen können, DFAs Sie weitere interessante Sprachen, die von wechselnden endgültig übersättigt)

_{Man sollte Lesen Sie die gefütterte Antwort, weil mein Ansatz zu einer Geldstrafe RE DFA in beiden Antwort ist anders}

Was ist ein Regulärer Ausdruck?

Der Ansatz unten erläutert Arden Therm, können anwendbar sein auf den übergang Diagramm, in dem es einzelne start-Zustand und es gibt keine null bewegen definiert (Unser DFA ist in dieser form). Diese Technik ist zu erklären, die in einem Buch: Formale Sprachen Und Automatentheorie

Erinnern 4.2 ARDEN-THEOREM:

Lassen B und C werden, sind zwei Reguläre Ausdrücke über Σ. Wenn C nicht enthalten Λ, dann für die Gleichung A = B + AC hat einen einzigartigen (und nur eine) Lösung A = BC*.

[Lösung]:

Schritt-1: Schreiben Sie das erste Gleichung, eine Gleichung für den entsprechenden Zustand im DFA. Diese Gleichung bedeutet, wie ein Zustand erreicht werden können in einem einzigen Schritt

So nach unserem DFA-4-Gleichungen sind möglich:

1. Q₀ = Λ + Q₁ + Q₃b
2. Q₁ = F₀ + F₂b
3. Q₂ = F₁b + Q₃eine
4. Q₃ = F₀b + Q₂eine

In der Gleichung (1) extra Λ ist, da Q₀ ist der Grundzustand erreicht werden können, ohne jegliche Eingabe (einem Punkt beginnen).
Da Q₀ ist auch nur ein Endzustand, der einen string bestehen aus a, b ist akzeptabel, wenn es endet bei Q₀. Wert von F₀ wird uns gewünschten regulären Ausdruck, so dass unser Ziel nicht ist, einfach Gleichung-(1) in Bezug auf a, b.

Schritt-2: Vereinfachen Sie die Gleichung mithilfe, indem Sie den Wert von Staaten, die aus anderen Gleichungen und mit Arden Vereinfachung der Gleichung.

Können wir zunächst die Gleichung-(4) und ersetzen Sie den Wert von F₂ aus Gleichung-(3).

Q₃ = F₀b + Q₂a

Q₃ = F₀b + (Q₁b + Q₃ - a)

Q₃ = F₀b + Q₁ba + Q₃aa

Die Letzte Gleichung kann, werden anzeigen in form von Arden Gleichung A = B + AC. Wo ist Q₃, B = Q₀b + Q₁ba und C = aa. Also laut Arden-therm Gleichung Q₃ = F₀b + Q₁ba + Q₃ - aa hat eine einzigartige Lösung:

Q₃ = (Q₀b + Q₁ba)(aa)*

Oder kann man schreiben wie folgt:

5. Q₃ = F₀b(aa)* + Q₁ba(aa)*

Logisch Sie überprüfen können/verstehen, eq-(5) bedeutet, dass Q₃ - kann auf zwei wegen erreicht werden (+) Faust ab durch die Anwendung b auf Q₀ dann gibt es eine Schleife mit label aa auf Q₃, der zweite Weg ist aus F₁ mit der Anwendung der ba.

In ähnlicher Weise können wir vereinfachen die Gleichung-(2)

Q₁ = F₀ + F₂b

Q₁ = F₀ - a + (F₁b + Q₃a)b

Q₁ = F₀ + Q₁bb + Q₃ab

Verwenden Arden Vereinfachung der Regeln hier.

Q₁ = (Q₀ + Q₃ - ab)(bb)*

weiter zu vereinfachen

6. Q₁ = F₀a(bb)* + Q₃ab(bb)*

Nun der Wert von F₃ aus Gleichung-(5) in Gleichung-(6)

Q₁ = F₀a(bb)* + (F₀b(aa)* + Q₁ba(aa)* )ab(bb)*

Q₁ = F₀a(bb)* + Q₀b(aa)* ab(bb)* + Q₁ba(aa)* ab(bb)*

Wieder verbessern diese Letzte Gleichung mit Arden Gesetz der Vereinfachung.

Q₁ = (Q₀a(bb)* + Q₀b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

nehmen Q₀ - Hochstapler:

7. Q₁ = F₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

Kann Sie verstehen, diese Gleichung, Seinen, wie Sie gehen, um F₁ aus-Zustand Q₀? Wir erinnern uns, diese Lösung als Gleichung-(7)

Wie oben können wir beurteilen den Wert von F₁ in Bezug auf die Staatliche F₀ und a, b, Ähnlich wie wir bewerten Wert für Zustand Q₃. Dazu können wir einfach den Wert von Zustand Q₁ aus Gleichung-(5) in Gleichung-(7).

5. Q₃ = F₀b(aa)* + Q₁ba(aa)*

. Q₃ = F₀b(aa)* + Q₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)*

8. Q₃ = F₀ ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* )

Nun in Gleichung Nummer (1) setzen Sie den Wert von Zustand Q₃ und F₁ aus Gleichung (8) und (7) receptively.

Q₀ = Λ + Q₁ + Q₃b

Q₀ = Λ + Q₀(a(bb)* + (aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + Q₀ ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* ) b

Nun, das Letzte mal anwenden Arden Lösung zu finden, die den Wert von Zustand Q₀ in Bezug auf die Symbole a und b.

Q₀ = Λ + ( (a(bb)* + (aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* ) b )*

dass ist das gleiche wie (können wir verwerfen Λ hier) RE:

( (a(bb)* + (aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* ) b )*

Dies ist das RE Sie gesucht haben.

Ich bin nicht sicher, es kann weiter vereinfacht werden. Ich bin verlassen, es ist wie eine übung für Sie.

In der verlinkten Frage, die ich vorgeschlagen, eine non-formale und analytische Methode, aber es war schwierig anzuwenden und finden ERNEUT für dieses DFA-und diese Frage zeigen, macht der Arden-Ungleichung und Schritt für Schritt Lösung.

Bearbeiten:

Meine Vorherige reguläre Ausdruck ist richtig, aber schwer zu Weintrauben, weil eine unsymmetrische form. Unten Schreibe ich die neue form des RE, die mehr symmetrisch.

Haben wir die Gleichung-(5), (6) wie folgt:

5. Q₃ = F₀b(aa)* + Q₁ba(aa)*

6. Q₁ = F₀a(bb)* + Q₃ab(bb)*

Beide sind symmetrisch im Aufbau und leicht zu erlernen. (Lesen Sie meinen Kommentar nach der eq-(5) oben)

Bewerten Wert von Zustand Q₁ in Bezug auf F₀, ich geputtet Wert von F₃ aus Gleichung-(5) in Gleichung-(6), dass gibt mir die Gleichung-(7) wie folgt:

7. Q₁ = F₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

Ähnlich, zu bewerten den Wert von Zustand Q₃ in Bezug auf F₀ können wir den Wert von F₁ aus Gleichung-(6) in die Gleichung-(5) , geben uns neue form der Gleichung-(8) wie folgt:

Q₃ = F₀b(aa)* + Q₁ba(aa)*

Q₃ = F₀b(aa)* + (F₀a(bb)* + Q₃ab(bb)* ) ba(aa)*

Q₃ = F₀b(aa)* + Q₀a(bb)* ba(aa)* + Q₃ab(bb)* ba(aa)*

Nun, wir können die Gleichung-(8) in die von uns gewünschte form:

8. Q₃ = F₀(b(aa)* + a(bb)* ba(aa)* )(ab(bb)* ba(aa)* )*

Nun haben wir die Gleichung-(1), (7), (8):

1. Q₀ = Λ + Q₁ + Q₃b

7. Q₁ = F₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

8. Q₃ = F₀(b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )*

Nun, wir können die Gleichung-(8) in die von uns gewünschte form:

8. Q₃ = F₀(b(aa)* + a(bb)* ba(aa)* )(ab(bb)* ba(aa)* )*

Nun haben wir die Gleichung-(1), (7), (8):

1. Q₀ = Λ + Q₁ + Q₃b

7. Q₁ = F₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

8. Q₃ = F₀(b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )*

Setzen Sie nun den Wert von Zustand Q₁ und F₃ in die Gleichung-(1):

Q₀ = Λ + Q₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + Q₀(b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )* b

kann auch geschrieben werden als:

Q₀ = Λ + Q₀ ( (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + (b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )* b )

Nächsten, gelten Arden ' s theorem in dieser Gleichung, und wir erhalten die endgültige RE:

Regulären Ausdruck für die geraden zahlen von 'a' und sogar zahlen von 'b':

( (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + (b(aa)* +
a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )* b )*

Können einen Schritt weiter vereinfacht wie folgt:

((a + b(aa)*ab)(bb)*(ba(aa)*ab(bb)*)*a + (b + a(bb)*ba)(aa)*(ab(bb)*ba(aa)*)*b)*

InformationsquelleAutor Grijesh Chauhan