Hi zusammen,
die F-Klausur rückt näher und die Fragen häufen sich *g* In einer der alten Klausuren habe ich folgende Aufgabe entdeckt, mit der ich recht wenig anfangen kann (WO steht das im Skript?).. bitte um Aufklärung!
Geben Sie mindestens 8 Methoden an, eine lambda-freie kontextfreie Sprache zu definieren.
Dann war da noch:
Wenden Sie das Pumping-Lemma auf folgende Sprache L an:
L = Anzahl des Buchstaben a in einem Wort über {a,b,c}* ist ganzzahlig und ein positives Vielfaches von b.
Reicht es (für volle Punktzahl), wenn ich das folgendermassen mache:
Angenommen, L wäre regulär.
Es ist w = aaabba € L, denn a ist 4x enthalten und b 2x. Sei n = 4. Dann ist eine Zerlegung von w:
u = aa
v = ab mit |uv| = 4 und
w = ba
Nach (iii) des Theorems muss gelten: uv^iw € L, aber uv^2w = aa(abab)ba ist kein Element von L, da a 5x und b 3x enthalten ist und da ist die Anzahl der a´s kein Vielfaches der b´s mehr.
Danke für eure Hilfe!
Hätte da auch nochmal ´ne Frage zum Nachweis von (Nicht-)Äquivalenzen in der PL: eine Äquivalenze bekomme ich ja zur Not über die Umformungsschritte hin. Aber wie würde ich folgende Aufgabe lösen:
F = P(x) ^ FürAlle x Q(x)
G = FürAlle x (P(x) ^ Q(x))
Zeige, dass F und G nicht äquivalent sind.
Danke schonmal
1. Frage:
n=4 kommt also nicht in Frage, das hast du korrekt ausgeschlossen,
wieso kann aber n nicht gleich 5, 6, 7, 8 oder gar 9 sein? oder 12.345?
schau dir mal ein Beispiel im Skript an, du musst das allgemein machen
'Sei n die Zahl des Pumpinglemmas, dann gibt es ein Wort c = a^n bb mit Länge > n für das folgende Zerlegung gilt usw.'
2. Frage:
sowas ist meist einfach: Beweis durch Beispiel,
denke dir für die Menge der x etwas handliches, etwa die Menge aller natürlichen Zahlen oder die Menge der 11 deutschen Loser in der Türkei
und für P(x) und Q(x) irgendwelche Beispielprädikate wie 'x ist gerade Zahl', 'x ist Primzahl', 'x ist < 1000', 'x ist Torwart', 'x ist ein schlechter Spieler' usw.
du suchst dir ein passendes Modell aus indem F wahr wird und G falsch oder andersrum -> Formeln nicht äquivalent
——–
P(x) ^ FürAlle x Q(x) bedeutet hier übrigens: P ist für irgendein x wahr und Q für alle x,
genauer: das x in P ist eine besondere Variable der man einen bestimmten Wert zu weisen muss
Beispiel:
U = Menge aller natürlichen Zahlen
x = 3
P(x) = (x >= 0)
Q(x) = (x durch 1 teilbar)
dieses Model haut noch nicht hin, aber wirst schon ein besseres finden ;)
'Sei n die Zahl des Pumpinglemmas, dann gibt es ein Wort c = a^n bb mit Länge > n für das folgende Zerlegung gilt usw.'
müsste es nicht heissen "es gibt ein c = a^kn b^n mit Länge > n und k>=2… ich sitz jetzt seit ´ner dreiviertel Stunde über dem kack Beweis. Das Beispiel im Skript ist mir relativ klar, aber hier geht´s ja um die Vielfachen der a´s. An dem Beispiel (n=4) ist mir ja schnell klar geworden, dass L nicht regulär sein kann.. aber wenn ich das formal machen soll, finde ich irendwie den Widerspruch nicht!! *schnief*
tja, es wird simpel wenn man das System erst mal drauf hat:
n ist diese Zahl,
dann wählt man das Wort a^2n b^n das du da vorschlägst,
(du musst da nicht kn nehmen sondern kannst konkret 2n auswählen, das ist erlaubt)
durch die Länge bestehen u und v nur aus a's, also v aus mindestens einem a
das Wort uv^0w = uw ist dann a^(2n-x) b^n (x >=1),
also offensichtlich nicht mehr in der Sprache, fertig
————
'ein positives Vielfaches von b' würde ich persönlich übrigens so interpretieren dass auch a^n b^n in der Sprache liegt,
dann funktioniert dass da oben nicht mehr (x könnte ja genau n sein),
aber dann geht der Spass eben folgendermaßen:
n ist diese Zahl,
a^n b^n liegt in L und ist > n lang
durch die Länge bestehen u und v nur aus a's, also v aus mindestens einem a
das Wort uv^0w = uw ist dann a^(n-x) b^n (x >=1),
also offensichtlich nicht mehr in der Sprache, fertig
Geben Sie mindestens 8 Methoden an, eine lambda-freie kontextfreie Sprache zu definieren.
Ich vermute mal, dass es bei den anzugebenden
Beschreibungsmitteln nicht verboten ist, dass
eines ein Spezialfall eines anderen ist (sonst
kämen, glaube ich, mit dem Stoff aus F2 keine
8 verschiedenen zusammen).
Also genügt hier wohl die Angabe irgenwelcher 8
der folgenden Methoden:
- Kontextfreie Grammatik
- Kontextfreie Grammatik in CNF (wegen der Lambda-Freiheit)
- Kontextfreie Grammatik in GNF (wegen der Lambda-Freiheit)
- L(A) für einen PDA A
- L(A) für einen buchstabierenden PDA A
- L(A) für einen fast-buchstabierenden PDA A
- N(A) für einen PDA A
- N(A) für einen buchstabierenden PDA A
- N(A) für einen fast-buchstabierenden PDA A
Hi zusammen! Hier noch eine Aufgabe, zu deren (potentieller) Lösung ich einige Zeit gebraucht habe.. jetzt würde ich gerne noch wissen, ob die auch stimmt *g*
Geben Sie eine Grammatik für folgende Menge an:
{uvu^rev | u Element {a,b}*, v Element {c,d}*, |uv| != 0}
Meine Grammatik sieht jetzt so aus:
S –> aSa | bSb | aAa | bAb | aa | bb | A
A –> cA | dA | c | d
hmm.. irgendwie kann ich nicht glauben, dass die stimmt.. aber ich finde auch kein Wort, das produziert werden könnte, das nicht in der Sprache ist.
Für eine Klausuraufgabe finde ich das recht fies… denn in der kurzen Zeit so ´ne "komplizierte" Grammatik zu finden… na, vielleicht hab ich einfach zu wenig Übung bisher!
Danke schon mal für eure Hilfe! :)
scheint zu stimmen, kannst dir auch noch ein bisschen sparen:
S –> aSa | bSb | aa | bb | A
A –> cA | dA | c | d
Geben Sie eine Grammatik für folgende Menge an:
{uvu^rev | u Element {a,b}*, v Element {c,d}*, |uv| != 0}
Meine Grammatik sieht jetzt so aus:
S –> aSa | bSb | aAa | bAb | aa | bb | A
A –> cA | dA | c | d
Kann mir jmd. erklären wie man bei einer solchen aufgabe vorgehen muss um zu einer lösung zu gelangen`?
2. Frage:
sowas ist meist einfach: Beweis durch Beispiel,
denke dir für die Menge der x etwas handliches, etwa die Menge aller natürlichen Zahlen oder die Menge der 11 deutschen Loser in der Türkei
und für P(x) und Q(x) irgendwelche Beispielprädikate wie 'x ist gerade Zahl', 'x ist Primzahl', 'x ist < 1000', 'x ist Torwart', 'x ist ein schlechter Spieler' usw.
du suchst dir ein passendes Modell aus indem F wahr wird und G falsch oder andersrum -> Formeln nicht äquivalent
Wäre das dann ein korrektes Modell:
U = Menge aller natürlichen Zahlen
x = 3
P(x) = (x ist Primzahl)
Q(x) = (jedes x hat einen Nachfolger)
