aus Klausur-Aufgaben
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Chomsky
Weiß net ob das Thema schonmal dran war, aber stimmt meine Lösung zur Klausur 9/2000, Aufgabe 7?
a) formale Definition Chomsky-Grammatik:
[color=blue]Eine Chomsky-Grammatik ist gegeben durch ein Quadrupel G = (T, N, P, S) mit:
endliche Mengen T, N: terminale/nichtterminale Symbole; T ∩ N = {}
V: Alphabet; V = T ∪ N
P: Produktionen; P ⊂ V* × V*
S: Startsymbol, S ∈ N[/color]
b) kontextfreie Regeln:
die 1. und 3.
c) kontextfreie Grammatik für gegebene Sprache:
[color=blue]Sprache etwas umschreiben: a[sup]n[/sup] b[sup]m[/sup] c a[sup]m[/sup] a[sup]n[/sup] | n ≥0, m ≥ 1
Produktionen:
S → aSa | A | ε
A → bAa | bca
Damit:
G = ({a, b, c}, {A, S}, {(S, aSa), (S, A), (S, ε), (A, bAa), (A, bca)}, S)[/color]
Ich werd mir noch mehr Aufgaben aus dem Bereich suchen, dazu später.
Ich hätte nur das anders formuliert:
P: {A}
T:{a,b,c}
L(G)={(S, aSa), (S, A), (A, bAa), (A, bca)}
Ausserdem darf S nicht auf ε hinauslaufen, da m ≥ 1
Was heisst die 1. und 3.?
Kapier ich nicht, aber ich glaube es ist ok, dass für alle p∈P gilt:
p∈ N x V*
Ach ja, und wäre dann die Produktion (ε, abc) auch erlaubt? ε ist ja in V*.
Und beüglich ableitbar:
x aus y mittels p direkt:
x=uvw ∧ y=uv’w ∧ (v,v’) ∈ P
wobei u,v,v’,w ∈ V*
x aus y direkt:
x → y , wobei p ∈ P
p
x aus y :
w1,…, wi ∈ V*;
x=w1;
y=wn;
(wi, wi+1) ∈ P für i = 1…n-1
Müssen wir sonst noch etwas wissen?
Kein (S, ε), klar.
dann schaust du in der Aufgabe nach, da sind 4 Beispiele gegeben. Davon sind meiner Meinung nach das 1. und das 3. kontextfrei.
nein, es heißt ja N × V*. Also irgendwas in der Art (N, V*). Und ε ist zwar in V*, aber nicht in N, und das muss zuerst kommen.
müssen wir DAS überhaupt wissen? Das ist mir irgendwie ne Nummer zu kompliziert. Hab es in TI schon nicht kapiert… Oder kann man das auch stark vereinfacht darstellen?
Also wenn du dir die alten Klausuren anschaust war immer das gleiche gefragt bei Chomsky-Gr.:
-Definition
-allgemein ableitbar, direkt ableitbar
-zusätzliche Bedinugn für kontextfreie Ch.-Gr
-Grammatik gegeben:Produktionen gesucht
-Produktionen geg.:…
Reicht hier nich auch einfach (x, y) ∈ P ?
Ist das nicht nur ein Sonderfall der folgenden Regel? Oder das gleiche wie die vorherige (wenn die das ist, was ich meine…)?
Das ist eine Art Verkettung von Produktionen, so wie die Transitivität der Relationen, oder?
Also was soll man hinschreiben wenns heißt direkt ableitbar?
Das kurze mit p ε P…
oder die lange Def.???
Weiss ich auch nicht, aber die kurze basiert auf der oberen langen Definition, also denk ich mal beides.
Auch net schlecht! 
Denke nicht, da wenn man produktion (x,y) hat, auch die wörter:
abcxcba → abcycba wird. Deshalb braucht man auch das was vor bzw hinter x/y steht.
Nein, ich hab praktisch oben x->y definiert (also mittels einer best.
p
Produktion p), und jetzt ist es egal, welche produktion es ist.
Genau, es sind endlich viele Produktionen hintereinander auf x angewendet. Wenn man (mit irgendeiner Reihung von Produktionen) auf y kommt, ist es ableitbar.
Str1ch4, was machst du denn hier für ein Durcheinander?
Also ich bin nach deiner Erklärung immer noch der Meinung, dass die letzte Form, die Verkettung der Produktionen, ausreicht, um die Ableitbarkeit zu beschreiben. Das 2. war ein Sonderfall (mit nämlich nur einer Produktion) und warum das 1. anders sein soll, kapier ich irgendwie net. Ob ich jetzt das u und w da lasse oder gar nicht erst erwähnt ist doch egal!
Und dein Beispiel mit “abcxcba → abcycba” stimmt doch und lässt sich meines Erachtens nach auch mit den anderen beiden Verfahren erklären. Vielleicht kann mir das mal einer im Detail erklären? Hab im Skript nix genaueres dazu gefunden.
lerns einfach mal 5 minuten, das geht schneller!
und ich denke auch, dass man fuer die direkte ableitbarkeit beide definitionen braucht.
Also sorry, das ich mich selbst Zitiert habe ,
also wenn du sagst: Das wort y ist aus x mit der Produktion (x,y) direkt ableitbar dann brauchst du nur die 1. Defintion.
Wenn du jetzt aber keine produktion angibst, also du sagst: “y ist aus x direkt ableitbar” dann musst du die 2. nehmen, welche als Vorraussetzung die 1. hat.
Und wenn du jetzt sagst “y aus x ableitbar”, musst du die 3. nehmen, welches als Vorraussetung 1 und 2 hat.
Ich habs auch nur aus dem Schöning abgeschrieben, und das muss dann ja wohl so stimmen.
hm, dann muss ich wohl mal da rein schauen.
ok, hab jetzt den unterschied zwischen “ableitbar” und “direkt ableitbar” erkannt. nur das mit dem u und w in der 1. definition will mir noch nicht so ganz einleuchten…
aehm Yves : du nix koennen produktion haben wo aus nem Terminalen Symbol (!) noch was ableitest … dat gehd nuesch … also ist auch nur eines dieser tollen beispiele richtig … schau nochmal nach !
Aus 99/10 Aufgabe 6b
Was soll man da hinschreiben, wenns heißt:Welche Sprache wird erzeugt?
Denke halt mal L(G) = {w ∈ T* | Anzahl a’s = Anzahl b’s}
Ich weiss nicht mehr wie das Zeichen dafür war, die Anzahl eines best. Buchstaben in einem Wort zu beschreiben, aber ich denke das oben würde auch taugen.
ich hab die aufgabe zwar net angeschaut … aber wenn die anzahl der buchstaben gleich ist kann man dann net schreiben
a^nb^n [verflucht ich weiss nicht wie man das in dem bbcode eingibt !!!]