| Die letzten 6 Beiträge |
| Alex |
Hallo
Ich hab:
S->AB
A->aAbbbb|epsilon
B->Bc|c
mhh könnte sein oder??
Freue mich auf antworten... |
| Friedrich |
Was weißt du über die Abschlusseigenschaft von KF Sprachen?
Sie sind abgeschlossen unter Vereinigung, Kleeneabschluss und Konkatenation (- jedoch nicht unter Komplement und Durchschnitt)
| Zitat: |
| L= { a^i b^j c^k| i,j,k >=0 und (i>=j oder j >= k)} |
Diese Definition besagt, dass folgende Wörter in der Sprache liegen:
Wörter mit mehr a's als b's
...mehr b'c als c's
...mit gleichvielen a b c
...
oder um es anders zu sagen:
alle Wörter über {a, b, c}* außer denjenigen wo mehr c als b UND mehr b als a vorkommen.
Wie gehen wir nun an das Problem heran, fragst du.
Aufgrund der Abschlusseigenschaft (Vereinigung) und dem "oder" in der Definition der Menge L können wir das Problem zerlegen (Divide & Conquer ;-) )
Mach doch mal eine Grammatik für
![[latex]L_{1} = \lbrace a^{i}b^{j}c^{k} | i <= j \rbrace[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_{1} = \lbrace a^{i}b^{j}c^{k} | i <= j \rbrace)
und eine für
![[latex]L_{1} = \lbrace a^{i}b^{j}c^{k} | j <= k \rbrace[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L_{1} = \lbrace a^{i}b^{j}c^{k} | j <= k \rbrace)
und vereine sie dann (ACHTUNG Nichtterminale müssen disjunkt sein!) |
| Tobias |
Weiß ich nicht. Ich habe keine Lust auf die Aufgabe. 
|
| foogi |
ja, und wie wäre es denn nun richtig? |
| Tobias |
![[latex]S \vdash EF \vdash bEcF \vdash bcF \vdash bcc[/latex]](http://www.matheboard.de/latex2png/latex2png.php?S \vdash EF \vdash bEcF \vdash bcF \vdash bcc)
Hier gilt:
![[latex]bcc = a^0b^1c^2 \in L(G) := \{ w \; | \; S \vdash^\ast w \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?bcc = a^0b^1c^2 \in L(G) := \{ w \; | \; S \vdash^\ast w \})
aber
![[latex]bcc = a^0b^1c^2 \notin L[/latex]](http://www.matheboard.de/latex2png/latex2png.php?bcc = a^0b^1c^2 \notin L) |
| foogi |
Angabe einer kontextfreien Grammatik
hallo,
ich möchte für folgende sprache eine KFG angeben. nun weiß ich nicht ob ich das so richtig gemacht habe, und dann wollte ich noch wissen ob es denn ein systematisches vorgehen dabei gibt? denn ich brauch da immer viel zu lange...
L= { a^i b^j c^k| i,j,k >=0 und (i>=j oder j >= k)}
also entweder muss a=b oder größer b sein oder b=c oder größer c.
da bin ich auf folgendes gekommen:
S -> AS | EF | G
A -> aAb |aA | epsilon
E -> bEc | bE | epsilon
F -> c
G -> aGc | Gc | epsilon
ist die Lösung den richtig? |
|
|
