Wie baue ich diesen endlichen Automaten?

Question

Ich studiere für einen Diskrete Mathematik Test und ich fand diese Übung, die ich nicht herausfinden kann.

"Erstellen Sie einen grundlegenden endlichen Automaten (DFA, NFA, NFA-Lambda) für die Sprache im Alphabet Sigma = {0,1,2} wo die Summe der Elemente in der Zeichenfolge ist gerade und diese Summe ist mehr als 3"

I Kleenes Satz mit verketten zwei Sprachen wie Verketten der einen Zusammenhang mit diesem regulären Ausdruck versucht:

(00 U 11 U 22 U 02 U 20)* - die auch Elemente

mit diesem

(22 U 1111 U 222 U 2222)* - diejenigen, deren Summe größer als 3 ist

Macht das irgendeinen Sinn ?? Ich denke, meine Regex sind schlaff.

Answer 1

Ich finde Ihre Notation etwas unscharf, vielleicht bin ich völlig falsch verstanden. Wenn dies der Fall ist, ignorieren Sie Folgendes. Es scheint, du bist noch nicht da:

• Ich nehme an, das * bedeutet '0 oder mehr mal'. Es muss jedoch einer der Strings mit der Summe> = 3 vorkommen. Es heißt, du brauchst ein + ('1 oder mehr Male').
• 112 und 211 fehlen in der Liste der Strings mit Summe> = 3.
• 222 und 2222 in dieser Liste sind überflüssig.
• Alle diese Strings können willkürlich mit 0s durchsetzt sein.
• Die Summe von 00 ist nicht mehr sogar als die Summe von 0.

---

Edit: wie diesem (nach ist der einzige Staat zu akzeptieren, dot-source):

automaton http://student.science.uva.nl/~sschroev/so/885411.png

Bei Staaten ein und c Die String-Summe ist immer ungerade. Bei Zuständen starten, b und acc die Summe ist immer gerade. Desweiteren, bei Start ist die Summe 0, bei b ist es 2 und bei d ist es> = 4. Das lässt sich recht einfach nachweisen. Daher erfüllt der akzeptierende Zustand acc alle Kriterien.

Edit 2: Ich würde sagen, das ist ein regulärer Ausdruck, der die gewünschte Sprache akzeptiert:

0*(2|(1(0|2)*1))(0*(2|(1(0|2)*1))+ 

Answer 2

Jeder Ausdruck, wie von Stephan geführt, sein kann:

(0 * U 2 * U 11) * - die Summen sogar

mit diesem einen

(22 U 11 U 222 U 112 U 211 U 121) + - diejenigen, deren Summe größer als 3

Ich weiß nicht, ob es mehr simplfied werden könnte, würde es helfen, den Automaten zu entwerfen.

Answer 3

Nicht sicher, ob dies Ihre Frage beantwortet, aber: müssen Sie einen regulären Ausdruck einreichen? oder wird ein FSM tun?

Auf jeden Fall kann es hilfreich sein, zunächst die FSM zu ziehen, und ich denke, das ist eine richtige DFA ist:

FSM http://img254.imageshack.us/img254/5324/fsm.png

Wenn das der Fall ist, wenn Sie Ihren regulären Ausdruck konstruieren (was, erinnere mich, hat eine andere Syntax als Programmierung "Regex"):

0*, um "0 so oft wie du willst" anzuzeigen. Dies ist sinnvoll, da 0 in Ihrem String den Zustand der Maschine nicht ändert. (Siehe in der FSM, 0 springt einfach zu sich selbst zurück)

Sie müssten die verschiedenen Kombinationen von "112" oder "22" usw. berücksichtigen - bis Sie mindestens 4 in Ihrer Summe erreichen.

Wenn Ihre Summe größer als 3 und gerade ist, dann würde (0 | 2) * Sie in einem Endzustand halten. Andernfalls (Summe> 3 und ungerade) würden Sie etwas wie 1 (0 | 2) * benötigen, um Sie in einen akzeptierenden Zustand zu versetzen.

(weiß nicht, ob das hilft, oder wenn sein Recht - aber es könnte ein Anfang sein)

Answer 4

Ich finde es einfacher, nur in Bezug auf die Staaten zu denken. Verwenden Sie fünf Zustände: 0, 1, 2, EVEN, ODD

Transitions:

State, Input -> New State 

(0, 0) -> 0 
(0, 1) -> 1 
(0, 2) -> 2 

(1, 0) -> 1 
(1, 1) -> 2 
(1, 2) -> ODD 

(2, 0) -> 2 
(2, 1) -> ODD 
(2, 2) -> EVEN 

(ODD, 0) -> ODD 
(ODD, 1) -> EVEN 
(ODD, 2) -> ODD 

(EVEN, 0) -> EVEN 
(EVEN, 1) -> ODD 
(EVEN, 2) -> EVEN 

Nur EVEN ist eine akzeptierende Zustand.