Den regelmäßigen Ausdruck dieses endlichen Automatons verstehen (und bilden)

Question

Für den obigen Automat ist der reguläre Ausdruck, der in meinem Lehrbuch angegeben wurde, der folgende:

a*(a*ba*ba*ba*)*(a+a*ba*ba*ba*)

Ich habe Probleme, dies abzuleiten ... Folgendes ist mein Versuch, es zu versuchen:

aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + ba*ba*ba*(ba*ba*ba*)*

Entweder bin ich falsch oder ich kann es nicht in der in dem Buch angegebenen Form vereinfachen. Kann mich jemand bitte hierher führen, auf den Fehler hinweisen oder ihn Schritt für Schritt erklären?

Ich würde das sehr dankbar und das schätzen.

Answer 1

Schau dir das an. Es präsentiert drei gute algorithmische Methoden zur Beantwortung von Fragen wie diese. Lernen Sie einen von ihnen oder alle drei, wenn Sie Zeit oder Neigung haben. Die Entfernung des Zustands ist ziemlich intuitiv, obwohl ich Kleenes transitives Verschlussmethode mag.

http://krchowdhary.com/toc/dfa-to-reg-exp.pdf

Bearbeiten: Ihr RE entspricht dem bereitgestellten. Hier ist die Reduzierung von ihnen auf Ihre:

0. a*(a*ba*ba*ba*)*(a+a*ba*ba*ba*)

1. = a*(a*ba*ba*ba*)*a + a*(a*ba*ba*ba*)*a*ba*ba*ba*

2. = a*(ba*ba*ba*)*a + a*(ba*ba*ba*)*ba*ba*ba*

3. = a*a + a*(ba*ba*ba*)*a + a*(ba*ba*ba*)*ba*ba*ba*

4. = aa* + a*(ba*ba*ba*)*ba*ba*ba*a + a*(ba*ba*ba*)*ba*ba*ba*

5. = aa* + a*(ba*ba*ba*)*ba*ba*ba*

6. = aa* + aa*(ba*ba*ba*)*ba*ba*ba* + (ba*ba*ba*)*ba*ba*ba*

7. = aa* + aa*(ba*ba*ba*)* + (ba*ba*ba*)*ba*ba*ba*

8. = aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + (ba*ba*ba*)*ba*ba*ba*

9. = aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + ba*ba*ba*(ba*ba*ba*)*

Schritt 1 ist richtig, da r (s + t) = rs + rt.

Schritt 2 ist richtig, da r*(r*sr*)*= r*(sr*)*.

Schritt 3 ist richtig, da r = r + s, wenn l (s) eine Teilmenge von L (R) ist.

Schritt 4 ist richtig, da r*r = rr*und rs + rq*s = rs + rqq*s.

Schritt 5 ist richtig, da Rs + r = r.

Schritt 6 ist richtig, da r*s = rr*s + s.

Schritt 7 ist richtig, da Rs + Rqq*S = RS + RQ*s.

Schritt 8 ist richtig, da r = r + s, wenn l (s) eine Teilmenge von L (R) ist.

Schritt 9 ist richtig, da r*r = rr*.

Bitte zögern Sie nicht, Fragen zu stellen oder auf Fehler hinweisen, die ich möglicherweise gemacht habe.

Edit2: Wenn Sie sich für solche Fragen interessieren, zeigen Sie etwas Liebe für die neue Informatik Stackexchange, indem Sie zu diesem Link gehen und sich engagieren !!!

http://area51.stackexchange.com/proposals/35636/computer-science-nonprogramming?referrer=rpnxa1_2bnyzxn85c5ibxq2

Answer 2

Das Lehrbuch scheint korrekt zu sein. Schritt für Schritt nehmen:

a*(a*

Wenn dieser Teil des regulären Ausdrucks wahr ist (mit anderen Worten, die Sie tatsächlich in einem 'a' lesen), wechseln Sie nach dem Rest des Ausdrucks: Nach dem Rest des Ausdrucks:

ba*

wird Sie in Zustand 2 haben,

ba*

in Staat 4 und

ba*

Wird Sie wieder in Zustand 3 haben.

Nehmen wir nun an, Sie haben in einem 'a' während dessen nicht gelesen a*(a*, das nächste lesen b Sie werden zu sagen. 2. Sie landen dann genau in der gleichen Situation wie zuvor und befolgen Sie den Rest a*ba*ba*) Sie landen wieder in Zustand 3.

Da Sie jetzt wieder in Status 3 sind, ist der Teil (a*ba*ba*ba*)* kann so oft ausführen, wie es will, da dies einfach das gleiche wie unser erstes Szenario sein wird (wo Sie in einem "a" während des Lesens gelesen werden a*(a*).

Der zweite Teil erklärt einfach das erste Szenario, in dem Sie mindestens einen 'a' lesen müssen, und dann ist der Rest der gleiche.

Ich hoffe, das hilft, lassen Sie mich wissen, ob es immer noch keinen Sinn ergibt. Ich weiß nicht, ob meine Erklärung zu klar ist.