gibt es reguläre Ausdrücke/endliche Automaten
für diese Sprachen?
- Palindrome
P = {w | w {a, b}*, w = reverse(w)}
-
E2 = {w | w {a, b}*,| w|a = | w|b}
-
E3 = {w | w {a, b, c}*,| w|a = | w|b = | w|c}
- K = korrekt geklammerte Ausdrücke (a = auf, b = zu)
NEIN! Beweis (Beispiel):
Falls es einen endlichen Automaten mit q Zuständen gibt,
der E2 akzeptiert, dann ...
Johannes Waldmann
2005-01-28