 Von einer Grammatik erzeugte Sprache |
gemuser
Grünschnabel
Dabei seit: 23.04.2011
Beiträge: 2
 |
|
| Von einer Grammatik erzeugte Sprache |
     |
Hallo,
habe folgende Aufgabe:
Welche Sprache wird von der Grammatik G={V, Z, P, S} erzeugt, mit:
V={S,B,C}
Z={a,b,c}
P: S --> aSBC | aBC
CB--> BC
aB--> ab
bB--> bb
bC--> bc
cC--> cc
Ich habe eine Antwort gefunden, aber der Lösungsweg ist nicht genug beschrieben:
L(G) = {(a^n)(b^n)(c^n) | n >=1}
Begründung:
S--> aSBC --> aaSBCBC --> aaaBCBCBC --> aaaBBCCBC --> aaaBBCBCC-->
aaaBBBCCC --> aaabBBCCC --> aaabbBCCC --> aaabbbCCC --->aaabbbcCC --> aaabbbccC ---> aaabbbccc
Wie kann man, aufgrund dieser Begründung, schlussfolgern dass L(G) die oben beschriebene Menge ist?
Es ist klar, dass das Wort aaabbbccc zur L(G) gehört, aber daraus kann man nicht schlussfolgern, dass L(G)=.... ist.
Muss man nicht zeigen, dass alle Wörter von L(G) diese Form haben? Gibt es einen bestimmten Lösungsweg? Für eine solche Aufgabe hat man nur 10 Minuten Zeit in einer Klausur... ist das nicht wenig?
Für jede Hilfe bin ich dankbar 
|
|
23.04.2011 12:56 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
| RE: Von einer Grammatik erzeugte Sprache |
|
Hallöchen,
der Beweis ist aus meiner Sicht wirklich nicht einfach, da ich prinzipiell ein Problem mit Beweisen habe
Um zu zeigen, dass die Grammatik die angegebene Sprache erzeugt, musst du die Äquivalenz beider Ausdrücke zeigen.
Dazu ist es wie üblich nötig, zu zeigen, dass ![[latex]a^nb^nc^n \in L(G)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?a^nb^nc^n \in L(G)) und jede Ableitung, die sich aus deinen Produktionen ergibt ein Wort aus ![[latex]a^nb^nc^n[/latex]](http://www.matheboard.de/latex2png/latex2png.php?a^nb^nc^n) ergibt.
Ich würde das definitiv nicht in 10 min in einer Klausur hinbekommen. Aber mit genügend training sieht man vlt die nötigen Schritte einfacher.
Mach mal ein paar vorschläge wie du rangehen würdest. Ich hoffe mal ich kann dir weiterhelfen. Habe ein Muster für den Beweis vorliegen.
VG,
Karlito
|
|
|
24.04.2011 19:07 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Vlt noch zur Info: Bei uns in der Klausur wurde kein Beweis dafür gefordert. Angeben der erzeugten Sprache reichte.
Denke in der Klausur kommen einfachere Beweise dran. Bei uns war es so gehalten, dass die Beweise zum bestehen nicht erforderlich waren, wohl jedoch, wenn man eine gute Note im Bereich 1,x oder ne gute 2 haben wollte.
Das kann natürlich je nach Prüfer und Uni variieren. Am besten mal den Dozenten oder einen Verantwortlichen fragen. Ältere Semester sind manchmal eine recht wenig objektive Quelle 
VG,
Karlito
|
|
|
24.04.2011 20:04 |
|
|
gemuser
Grünschnabel
Dabei seit: 23.04.2011
Beiträge: 2
|
|
| Zitat: |
Original von Karlito
Vlt noch zur Info: Bei uns in der Klausur wurde kein Beweis dafür gefordert. Angeben der erzeugten Sprache reichte. |
Ja, das wurde mir auch gesagt.... D.h. es reicht, wenn man ein paar Wörter schreibt, warum er denkt, dass die Grammatik die Sprache erzeugt. Ich finde es irgendwie nicht so korrekt, denn man muss beweisen was man schreibt... Aber wenn das so reicht, dann machen wir auch so.
Danke für deine Antworten.
|
|
|
25.04.2011 10:42 |
|
|
|
