Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Eine kontextfreie Grammatik für eine Sprache (http://www.informatikerboard.de/board/thread.php?threadid=126)

Geschrieben von foogi am 10.01.2007 um 10:39:

  Eine kontextfreie Grammatik für eine Sprache

hallo,

gibt es ein systematisches Vorgehen, wenn man eine kontextfreie Grammatik für eine Sprache angben möchte?

ich möchte für diese Sprache:

L={a^i b^j c^k |i,j,k >=0 und (i>=j oder j>=k)}

eine kontextfreie Grammatik angeben.
Ich komme da auf keine Lösung, vor allem weiß ich nicht wie man da systematisch vorgehen kann..?


Geschrieben von ed209 am 10.01.2007 um 22:23:

 

Eine vernünftige systematische Lösung gibt es leider nicht, aber ich kann dir für diese Sprache einen Tip geben:

Schau dir die Bedingung mal an. Du kannst die Sprache auch als Vereinigung von zwei (einfacheren) Sprachen hinschreiben.

Gruß,
ED


Geschrieben von foogi am 10.01.2007 um 22:33:

 

hallo,

und wie könnte das konkret aussehen?
verwirrt


Geschrieben von ed209 am 12.01.2007 um 21:02:

 

Du kannst bei den Bedingungen einmal de Morgan anwenden (und das "oder" ausklammern) und dann die Definition der Vereinigung von Mengen hernehmen.
Die war zumindest bei uns: [latex] X \cup Y = \{z | z \in X \lor z \in Y\} [/latex]


Geschrieben von foogi am 15.01.2007 um 15:26:

 

hallo,

ich hatte folgende Sprache:

L={a^i b^j c^k |i,j,k >=0 und (i>=j oder j>=k)}

ich wäre auf folgende Lösung gekommen:

S--> A | B

A --> aAb | aA | epsilon

B --> bBc | bB | epsilon

da ja nur eine der Bedingungen erfüllt sein muss, müsste es doch richtig sein oder was meint Ihr dazu?

danke


Geschrieben von ggg am 14.12.2018 um 12:52:

 

nega


Forensoftware: Burning Board, entwickelt von WoltLab GmbH