Konstruieren eines regulären Ausdrucks aus einem endlichen Automaten

Ich versuche, einen regulären Ausdruck aus einem Finite Automaton zu konstruieren, fand aber mein Selbst völlig bei diesem fest. Die zu verwendende Regex ist wie folgt:Konstruieren eines regulären Ausdrucks aus einem endlichen Automaten

? = 0 oder 1
* = 0 oder mehr
+ = 1 oder mehr
| = Oder
_ = leere Zeichenkette
@ = leere Menge
() = Klammern

Wie ich die Saiten verstehen entweder "b *" endet mit einem "*" oder enden mit sein muss "a + bb +"
Was ich jetzt habe, ist ((b*(a+(bb))*)*) , aber das berücksichtigt keine Zeichenfolge, die mit 'a' endet.

Wie gesagt, ich bin zu 100% damit beschäftigt und kann einfach nicht verstehen, wie ich damit arbeiten soll.

Bild: http://img593.imageshack.us/img593/2563/28438387.jpg

Code:
Typ des Automaten
FA

Staaten
q1
q2
q3
q4

Alphabet
ein
b

Ausgangszustand
q3

Endzustände
q3
q4

Transitions
q1 ein q2
q1 b q3
q2 ein q2
q2 b q2
q3 ein q4
q3 b q3
q4 ein q4
q4 b q1

Alle Lösungen oder Tipps zu schätzen!

Quelle

2010-12-20 mjuopperi

Was ist mit 'b * (a +)? (Bb + | bb + a +)?'? – dheerosaur

Beschuldigen Sie, dass ich feststeckt, weil ich nie daran gedacht habe, "(a +)?" Zu verwenden! Vielen Dank! Obwohl ich sicherstellen muss, würde das "babbabb" oder "abbaabb" akzeptieren? (dh mehr als eine "Runde" machen) – mjuopperi

Sorry, '(a +)?' ist formell äquivalent zu 'a *' –

Es ist nicht möglich, von q2 in einen Endzustand zu gelangen. Entfernen Sie es und das resultierende DFA sollte einfacher zu konvertieren sein.

Wie ich verstehe die Saiten entweder "b *" endet mit einem "*" oder enden mit "a + bb +" i jetzt Was sein muss ist ((b * (a + (bb)) )), aber das berücksichtigt keine Zeichenfolge, die mit 'a' endet.

Stellen Sie sich vor q3 war kein Endzustand und q4 war der Ausgangszustand. Wie würde der Regex dann aussehen?Das zu ändern, was Sie wollen, sollte nicht zu schwer sein, haben Sie einfach keine Angst, denselben Zustand und/oder dieselben Übergänge zu haben, die von mehr als einem Teil der Regex beschrieben werden. Ein weiterer Tipp: Ich bin mir ziemlich sicher, dass Sie entweder ? oder | mindestens einmal verwenden müssen.

Quelle

2010-12-20 16:04:56

Ich habe q2 im Grunde ignoriert und dachte nur, dass "ab" mindestens noch eins folgen muss "b ". (Also das "Ende mit" a + bb + "") – mjuopperi

@Gawwad Ok, ich habe weitere Hinweise hinzugefügt, basierend auf dem spezifischen Problem, das du in deiner Frage erwähnt hast. –

Wäre es "(a * (bb + a +)?) *"? Soll ich() * um die "Runde" herum Zeichenfolgen wie "abbaabb" berücksichtigen oder ist das notwendig? – mjuopperi

Wenn Sie dies Werkzeuge für Automaten füttern (z.B. Vcsn), würden Sie diese:

In [1]: import vcsn 

In [2]: %%automaton a 
    ...: $ -> q3 
    ...: q1 -> q2 a 
    ...: q1 -> q3 b 
    ...: q2 -> q2 a 
    ...: q2 -> q2 b 
    ...: q3 -> q4 a 
    ...: q3 -> q3 b 
    ...: q4 -> q4 a 
    ...: q4 -> q1 b 
    ...: q3 -> $ 
    ...: q4 -> $ 
    ...: 
mutable_automaton<letterset<char_letters(ab)>, b> 

In [3]: a.expression() 
Out[3]: (b+aa*bb)*(\e+aa*)

wo \e die leere Zeichenkette bezeichnet. Dann ist es nur ein Problem der Syntaxkonvertierung.

Grafisch:

Siehe this example live und Spielzeug mit ihm.

Quelle

2015-05-22 07:38:54 akim

Konstruieren eines regulären Ausdrucks aus einem endlichen Automaten

Antwort

Verwandte Themen