Pumping-Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweisen Sie mit dem Pumping-Lemma für kontextfreie Sprachen, dass folgende Sprache
[mm] [center]$L=\{a^{n}b^{k}c^{l}|n,k,l \in \IN \wedge n \le min(k,l)\}$[/center]
[/mm]
nicht kontextfrei ist. |
Hallo! Da dies mein erster Beitrag in diesem Forum ist, hoffe ich, dass ich alles richtig mache.
Wir haben als Hausaufgabe die obige Aufgabe gestellt bekommen. Wie das Pumping-Lemma funktioniert ist mir eigentlich klar. Mir fällt es allerdings schwer, ein Wort $w$ zu finden, was ich entsprechend "aufpumpen" kann.
Probiert habe ich es bereits mit
[mm] $w=a^{n}b^{n}c^{n}$ [/mm] und [mm] $w=a^{n}b^{n}c^{l}$
[/mm]
leider erfolglos, da immer Fälle entstehen in denen dieses Wort funktioniert. Für das erste funktioniert z.B. [mm] $a^{n+i}b^{n+j}c^n$. [/mm] Für $j=0$ klappt es, für $i=0$ jedoch nicht.
Hat vielleicht einer von euch eine Idee, was man hier wählen muss? Vielleicht sieht es einer ja besser wie ich.
Auf alle Fälle danke, dass ihr euch Zeit hierfür nehmt!
---
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Di 27.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
