Informatiker Board | Theoretische Informatik | Angabe einer kontextfreien Grammatik

Informatiker Board » Themengebiete » Theoretische Informatik » Angabe einer kontextfreien Grammatik

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Angabe einer kontextfreien Grammatik

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

foogi
Jungspund

Dabei seit: 06.01.2007
Beiträge: 19

Angabe einer kontextfreien Grammatik

Zitatantwort auf diesen Beitrag erstellen

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?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von foogi: 29.01.2007 17:29.

29.01.2007 17:28

Nehmen Sie foogi in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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

30.01.2007 00:56

Nehmen Sie Tobias in Ihre Freundesliste auf

foogi
Jungspund

Dabei seit: 06.01.2007
Beiträge: 19

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

31.01.2007 15:38

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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

31.01.2007 19:08

Friedrich Friedrich ist männlich

Grünschnabel

Dabei seit: 09.12.2006
Beiträge: 9

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!)

__________________
$[latex]Informatiker \neq Programmierer[/latex]$

02.02.2007 23:23

Nehmen Sie Friedrich in Ihre Freundesliste auf

Alex
unregistriert

Hallo

Ich hab:

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

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

23.06.2011 11:40

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Angabe einer kontextfreien Grammatik