Angabe einer kontextfreien Grammatik

29.01.2007, 17:28

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?

30.01.2007, 00:56

Auf diesen Beitrag antworten »

Tobias

$[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]$

31.01.2007, 15:38

Auf diesen Beitrag antworten »

foogi

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

31.01.2007, 19:08

Auf diesen Beitrag antworten »

Tobias

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

02.02.2007, 23:23

Auf diesen Beitrag 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]$
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!)

23.06.2011, 11:40

Auf diesen Beitrag antworten »

Alex

Hallo

Ich hab:

S->AB
A->aAbbbb|epsilon
B->Bc|c

mhh könnte sein oder??
Freue mich auf antworten...

Neue Frage »

Antworten »

Angabe einer kontextfreien Grammatik

Verwandte Themen