Sprache kontextfrei? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:50 Fr 24.03.2006 | | Autor: | armani |
| Aufgabe 1 | Wo liegt die Sprache [mm] L_2 [/mm] = [mm] {a^ib^jc^l ; i . j < l} [/mm] in der folgenden Hierarchie?
reguläre Sprachen,kontextfreie Sprache,NP,entscheidbare Sprache,unentscheidbare Sprache.
|
| Aufgabe 2 | | Wo liegt die Sprache [mm] L_1 [/mm] = {w [mm] \in [/mm] {a,b,c}^* ; in jedem Prafix von w kommen mindestens zwei der Buchstaben a,b,c gleich oft vor} |
Hallo,
Ich stehe vor der Klausur nächste Woche und habe ein Problem bei diesen Aufgaben.
Also für die Aufgabe 1 ,wenn i < j < l kann ich mit Pumping Lemma beweisen,dass die Sprache nicht kontextfrei ist.Aber hier konnte ich keinen Weg finden.Meiner Meinung nach ist diese Sprache kontextfrei und somit muss ich ein Kelller Automat dafür finden,aber ich bin mir nicht so sicher.
Für die Aufgabe 2 bin ich der Meinung das die Sprache regulär ist und versuche gerade ein Automat zu bauen.
Danke für weitere Hilfe
Gruss
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Hallo und guten Morgen,
zu Aufgabe 1:
[mm] L_2=\{a^ib^jc^k\:\ | i\cdot j
Falls [mm] L_2 [/mm] kontextfrei, so gibt es nach dem Pumping-Lemma für kontextfreie Sprachen ein n so, dass
wir jedes [mm] z\in L_2 [/mm] mit [mm] |z|\geq [/mm] n zerlegen können in
z=uvwxy
mit
(1) [mm] |vx|\geq [/mm] 1
(2) [mm] |vwx|\leq [/mm] n
(3) für alle [mm] i\geq [/mm] 0 gilt [mm] uv^iwx^iy\in [/mm] L
Wenn i,j,k groß genug wählen, so können wir [mm] vwx=c^{k'} [/mm] für ein k' wählen,
also kann man Nicht-Kontextfreiheit von [mm] L_2 [/mm] nicht via Pumping-Lemma direkt zeigen.
Man sollte vielleicht versuchen, Nicht-Kontextfreiheit ueber die Anwendung des sog. Odgen-Lemmas zu zeigen
(siehe Hopcroft-Ullman), das ist sozusagen eine strengere Version des Pumping-lemmas:
Odgen-Lemma:
Sei L kontextfrei. Dann gibt es n so, dass für jedes [mm] z\in [/mm] L, in dem wir n oder mehr Positionen in z als unterschiedlich
markieren koennen, z geschrieben werden kann als z=uvwxy mit
(1) v und x haben zusammen mindestens eine markierte Position.
(2) vwx hat höchstens n markierte Positionen
(3) Fuer alle [mm] i\geq [/mm] 0 gilt uv^iwx^iy [mm] \in [/mm] L
Wählen wir nun [mm] a^ib^jc^k\in [/mm] L gross genug und markieren wir die a's, so liefert dies dann einen Widerspruch zum Odgen-Lemma
(weder v noch x dürfen zwei verschiedene Symbole enthalten, und dann fliegt einem einfach die Länge des ''a-b''-Teils um die Ohren.  ).
Zu Aufgabe 2:
Ich würd sagen, es sollte heissen: ''in jedem Praefix gerader Länge'', denn sonst enthielte [mm] L_1 [/mm] nur die
leere Zeichenkette (oder wäre die leere Menge), denn wir müssten die Bedingung für das erste Symbol des Wortes erfüllen.
Wir können uns in einer endlichen Zustandsmenge merken, welche der drei Anzahlen der Vorkommen von a, b, c gleich sind (nach je zwei Schritten).
Wenn nun an einer geraden Stelle Anz(a)=Anz(b) ist und Anz(c) um mehr als zwei davon abweicht, können wir nur noch in jeder Phase von zwei aufeinanderfolgenden
Schritten entweder c's anfügen oder ein a und ein b, sonst verletzen wir die Bedingung.
Dies sollte eine skizzenhafte Konstruktionsanleitung fuer einen det. Automaten sein, daher wäre dann [mm] L_1 [/mm] regulär.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:27 Mi 29.03.2006 | | Autor: | armani |
Zuerst Danke an Mathias.Unser Professor hat das Odge Lemma in der Vorlesung und Übung gar nicht behandelt,deshalb konnte ich mir gar nicht vorstellen,wie solche Aufgabe wie die Aufgabe 1 in Klausur vorkommen kann wenn man nicht mit Pumping beweisen kann(aber die war Klausur Aufgabe von letzten Jahr).Jetzt bemühe ich mich ein TM dafür zu bauen.
Gruss und danke noch mal
|
|
|
|
