Beweis kontextfreie Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:39 Di 25.02.2014 | | Autor: | marcel25 |
| Aufgabe | | Ist die Sprache L = [mm] {a^n b^m a^n a^m | n,m > 0} [/mm] kontextfrei? Beweisen Sie Ihre Antwort! |
Mir ist durch eine Überlegung über einen Kellerautomaten Klar das diese Sprache nicht kontextfrei sein kann. Allerdings kann ich das durch einen Beweis mit dem puming lemma nicht Belegen.
Bei der Durchführung eines Widerspruchsbeweises mit dem pumping lemma hab ich folgendes Problem.
Wenn ich v und x die b's zuordne kann ich solange "pumpen" wie ich will und es ergibt sich kein Widerspruch. Aber es muss ja jeder Fall einen Widerspruch erzeugen.
Kann jemand meinen denkfehler identifizieren ?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:44 Di 25.02.2014 | | Autor: | tobit09 |
Hallo marcel25 und herzlich ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
> Ist die Sprache L = [mm]{a^n b^m a^n a^m | n,m > 0}[/mm]
> kontextfrei? Beweisen Sie Ihre Antwort!
> Mir ist durch eine Überlegung über einen Kellerautomaten
> Klar das diese Sprache nicht kontextfrei sein kann.
Doch, diese Sprache ist kontextfrei.
Beachte dazu [mm] $a^na^m=a^ma^n$ [/mm] für alle [mm] $n,m\in\IN$.
[/mm]
Viele Grüße
Tobias
|
|
|
|
