Come posso costruire questo automa finito?

Question

Sto studiando per un test di matematica discreta e ho trovato questo esercizio che non riesco a risolvere.

"Costruisci un automa finito di base (DFA,NFA,NFA-lambda) per la lingua nell'alfabeto Sigma = {0,1,2} dove la somma degli elementi nella stringa è pari E questa somma è maggiore di 3"

Ho provato a utilizzare il Teorema di Kleene concatenando due linguaggi come concatenare quello associato a questa espressione regolare:

(00 U 11 U 22 U 02 U 20)* - gli elementi pari

con questo

(22 U 1111 U 222 U 2222)* - quelli la cui somma è maggiore di 3

Ha qualche senso??Penso che le mie espressioni regolari siano flaccide.

Answer 1

Trovo la vostra notazione un po 'sfocata, così forse io sono completamente malinteso. In tal caso, ignorare quanto segue. Sembra che non ci sei ancora:

• presumo i mezzi * '0 o più volte'. Tuttavia, deve verificarsi una delle stringhe con somma> = 3. E 'dire che serve a + ( '1 o più volte').
• 112 e 211 mancano nella lista di stringhe con somma> = 3.
• 222 e 2222 in quella lista sono superflui.
• Tutte queste stringhe può essere arbitraryly intervallati da 0s.
• La somma di 00 non è più uniforme rispetto alla somma delle 0.

---

Modifica che ne dite di questo ( acc è stato solo accettare, dot-source):

automa http://student.science.uva.nl/~ sschroev / così / 885411.png

A Uniti a e c la somma stringa è sempre dispari. A Uniti start , b e acc la somma è sempre pari. Inoltre, a start la somma è 0, a b è 2 ea d è> = 4. Questo può essere dimostrato piuttosto facilmente . Quindi lo stato accettando acc soddisfa tutti i criteri.

Modifica 2: Direi che questo è un regex che accetta la lingua richiesta:

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

Answer 2

Non sono sicuro che questo risponda alla tua domanda, ma:è necessario inviare un'espressione regolare?o andrà bene un FSM?

In ogni caso, potrebbe essere utile disegnare prima il FSM, e io pensare questo è un DFA corretto:

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

Se è così, quando costruisci la tua espressione regolare (che, ricorda, ha una sintassi diversa rispetto alla programmazione di "regex"):

0* per indicare "0 quante volte vuoi".Questo ha senso, poiché 0 nella stringa non cambia lo stato della macchina.(Vedi, nell'FSM, 0 torna semplicemente su se stesso)

Dovresti tenere conto delle diverse combinazioni di "112" o "22" ecc. - finché non raggiungi almeno 4 nella tua somma.

Se la tua somma è maggiore di 3, o pari, allora (0|2)* ti manterrebbe allo stato finale.Altrimenti (somma > 3 e dispari) avresti bisogno di qualcosa come 1(0|2)* per metterti in uno stato di accettazione.

(non so se aiuta o se è giusto, ma potrebbe essere un inizio!)

Answer 3

Ogni espressione, come guidati da Stephan, può essere:

(0 * U * 2 U 11) * - le somme anche

con questo

(22 U 11 U 222 U 112 U 211 U 121) + - quelli la cui somma è superiore a 3

Non so se potesse essere semplificazioni rese più, sarebbe utile progettare l'automa.

Answer 4

Lo trovo più facile solo a pensare in termini di stati. Utilizzare cinque stati: 0, 1, 2, PARI, DISPARI

Transizioni:

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

, anche se solo è uno stato di accettazione.