Endlicher Automat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo, Leute!
Ich brauche dringend eure Hilfe! Ich habe zwei Aufgaben und schreibe morgen den Test, ich weiß aber nicht, wie sie richtig zu lösen sind
Die Aufgaben sind:
1)Es sei L die Sprache eines endlichen Automaten und [mm] L_{r} [/mm] die Sprache, die aus allen umgekehrten Wörtern von L besteht. Gibt es zu jedem endlichen Automaten EA mit einer Sprache L einen endlichen Automaten [mm] Ea_{r}, [/mm] der [mm] L_{r} [/mm] akzeptiert?
2)Es sei L={w [mm] \in{a,b}*| [/mm] w enthaelt mehr a's als b's}. Gibt es einen endlichen Automaten EA mit L(EA)=L?
Ich danke für eure Beteiligung und Hilfe im vorraus
|
|
| |
|
Hallo,
ich würde es so angehen:
1) Wir wissen, dass die Sprache regulär ist. Zu jeder regulären Sprache lässt sich eine linkslineare Grammatik angeben. Wenn du nun einfach jede Produktionsregel umdrehst, dann bekommst du eine rechtslineare Grammatik, die dir die umgekehrten Wörter der usrprünglichen Grammatik produziert. Da die so erzeugte Sprache auch regulär ist, gibt es auch einen endlichen Automaten, der sie akzeptiert.
2) Hier würde ich versuchen, mit dem Pumping Lemma zu zeigen, dass die Aussage falsch ist.
Es sind nur Ideen, ich habe sie nicht groß überprüft, aber das kannst du ja mal versuchen.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:25 Di 04.12.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
