Informatiker Board | Druckvorschau: Angabe einer kontextfreien Grammatik

Geschrieben von foogi am 29.01.2007 um 17:28:

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?

Geschrieben von Tobias am 30.01.2007 um 00:56:

$[latex]S \vdash EF \vdash bEcF \vdash bcF \vdash bcc[/latex]$

Hier gilt:

$[latex]bcc = a^0b^1c^2 \in L(G) := \{ w \; | \; S \vdash^\ast w \}[/latex]$

aber

$[latex]bcc = a^0b^1c^2 \notin L[/latex]$

Geschrieben von foogi am 31.01.2007 um 15:38:

ja, und wie wäre es denn nun richtig?

Geschrieben von Tobias am 31.01.2007 um 19:08:

Weiß ich nicht. Ich habe keine Lust auf die Aufgabe. geschockt

Geschrieben von Friedrich am 02.02.2007 um 23:23:

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]$
und eine für
$[latex]L_{1} = \lbrace a^{i}b^{j}c^{k} | j <= k \rbrace[/latex]$
und vereine sie dann (ACHTUNG Nichtterminale müssen disjunkt sein!)