palindrome automaten < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:55 Mi 29.10.2008 | | Autor: | AriR |
hey leute,
gibt es einen endlichen automaten (also einen automaten ohne speicher) der die sprache der palindrome akzeptiert? ich komm nach ewigem versuchen auf keinen automaten und würde sagen nein, nur wie begründe ich das?
hierbei sind palindrome wörter die von vorne und hinten gelesen gleich sind wie abbb, aba, arttra usw :)
danke schonmal im voraus. gruß :)
|
|
| |
|
Hallo "0!
> hey leute,
> gibt es einen endlichen automaten (also einen automaten
> ohne speicher) der die sprache der palindrome akzeptiert?
> ich komm nach ewigem versuchen auf keinen automaten und
> würde sagen nein, nur wie begründe ich das?
Wie hast du das denn versucht? Mag sein, dass es an der Endlichkeit scheitert, aber ich würde es so probieren:
Nennen wir dein Alphabet [mm] \Sigma=\{a,b\}, [/mm] dann gibt es vom Startzustand aus zwei Möglichkeiten - entweder mit a in Zustand 1 oder mit b in Zustand 2. Wenn du in Zustand 1 bist, muss das letzte Zeichen, dass du liest, wieder ein a sein, in Zustand 2 entsprechend ein b. Das heißt, du hättest ab jetzt zwei unterschiedliche Wege, wobei man von dem einen nicht mehr in den anderen kann. Beim zweiten Zeichen ergeben sich dann jeweils wieder zwei Wege usw.. Probier mal, ob du damit weiter kommst, oder woran das scheitert.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:21 Fr 31.10.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
