Pumping Lemma kontextfrei < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen oder widerlegen Sie, dass die folgende Sprache kontextfrei ist.
[mm] $L=\{w | w \in \{a,b\}^{\*}\text{ mindestens so viele a's wie b's}\}$ [/mm] |
Behauptung: L ist nicht kontextfrei.
Sei [mm]L[/mm] eine kontextfreie Sprache, dann gibt es eine
Konstante [mm]n \in \mathbb N[/mm], so dass sich jedes [mm]z \in L[/mm] mit
[mm]|z|\geq n[/mm], so als z=uvwxy schreiben lässt, dass [mm]|vwx|\leq n[/mm],
[mm]|vx|\geq 1[/mm] und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm]
gilt:
wähle: $z=w=aaabbb [mm] \in [/mm] L$
Dieses Wort sollte jedenfalls in der Sprache liegen. Mir ist natürlich auch klar, dass diese Sprache nicht kontextfrei ist. Kann man mit dem PL zeigen, DASS die Sprache kontextfrei IST? Wenn nicht, wie macht man das dann hier?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:10 Do 23.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
leider habe ich im Moment nicht die Zeit, mir das genau zu überlegen. Aber ich gehe davon aus, dass diese Sprache kontextfrei ist. Zum Nachweis gebe eine kontextfreie Grammatik $G$ mit $L(G)=L$ an (und weise natürlich $L(G)=L$ nach).
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Fr 24.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:04 Fr 24.05.2013 | | Autor: | tobit09 |
Hallo nochmal,
in der Tat ist die Sprache kontextfrei.
Eine kontextfreie Grammatik für diese Sprache ist z.B. gegeben durch die Produktionsregeln
[mm] $S\to\varepsilon|aSbS|bSaS|aS$.
[/mm]
Den Beweis, dass tatsächlich alle Wörter aus $L$ von dieser Grammatik erzeugt werden können, ist allerdings offenbar aufwendig.
Ob es einen leichteren Weg gibt, die Sprache als kontextfrei nachzuweisen, weiß ich nicht.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:39 Fr 24.05.2013 | | Autor: | bandchef |
Wir haben die Aufgabe mittlerweile auch in der Schule gelöst. Unser Prof. hat es genauso gemacht, wie du und einfach eine Grammatik erstellt.
|
|
|
|
