Reguläre Ausdrücke < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | (b|c)*(abb)*<=>(b|c|abb)* |
Gibt es ein Onlinetool, dass zwei oder mehr reguläre Ausdrücke auf Äquivalenz prüft?
Und natürlich der obligatorische Satz:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
kann man doch eigentlich selber nachprüfen ob die das selbe erzeugen ;)
NFA bestimmen, dann DFA, dann minimieren und dann nach Isomorphie der Zustände überprüfen..
Spaß beiseite, kann dir leider nicht sagen ob es so was gibt, aber ich muss einfach wissen, die regulären Ausdrücke die du da hingeschrieben hast, die sind doch nicht gleich oder?
beim ersten kannst du zum beispiel
abbb nicht erzeugen, beim zweiten aber schon
miau:3
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:22 Do 19.05.2011 | | Autor: | felixf |
Moin!
> (b|c)*(abb)*<=>(b|c|abb)*
> Gibt es ein Onlinetool, dass zwei oder mehr reguläre
> Ausdrücke auf Äquivalenz prüft?
Ein Online-Tool kenn ich nicht.
Allerdings: zu einem regulaeren Ausdruck kannst du einen NFA konstruieren, dazu einen DFA und schliesslich einen minimalen DFA. Dazu gibt es jeweils Algorithmen.
Der minimale DFA ist nun eine Invariante (bis auf Isomorphe) der regulaeren Sprache: haben zwei regulaere Sprachen einen isomorphen minimalen DFA, so sind sie gleich.
Wenn du also die minimalen DFAs berechnen kannst, musst du schauen ob sie isomorph sind oder nicht. Das sagt dir dann ob die urspruenglichen regulaeren Ausdruecke aequivalent sind oder nicht.
LG Felix
|
|
|
|
