kontextfreie Sprache in PDA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 23:17 Mi 18.06.2008 | | Autor: | balboa |
| Aufgabe | Gegeben ist die Sprache:
[mm]L := \{td^n | n \ge 1, t \in \{a,b\}^\*[/mm] und [mm]\#_a(t) = n\} \cup \{te^n | n \ge 1, t \in \{a,b\}^\*[/mm] und [mm]\#_b(t) = n\}[/mm]
Die Sprache ist deterministisch kontextfrei; zeige dies, indem ein deterministischer PDA angegeben wird, der die Sprache erkennt. Erläutere die Konstruktion (vor allem die Funktion der einzelnen Zustände des PDA). Gib weiterhin eine kurze Begründung an, warum die Sprache nicht durch einen PDA ohne Epsilon-Übergänge erkannt werden kann. |
Leider stehe ich bei dieser Aufgabe vollständig ohne Idee da und weiß nicht, wie ich zu einer Lösung kommen soll.
Helft mir bitte weiter, danke!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:35 Di 24.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
