Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Eine kontextfreie Grammatik für eine Sprache » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Eine kontextfreie Grammatik für eine Sprache
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
foogi
Jungspund


Dabei seit: 06.01.2007
Beiträge: 19

Eine kontextfreie Grammatik für eine Sprache Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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..?
10.01.2007 10:39 foogi ist offline E-Mail an foogi senden Beiträge von foogi suchen Nehmen Sie foogi in Ihre Freundesliste auf
ed209
Routinier


Dabei seit: 07.09.2006
Beiträge: 308

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
10.01.2007 22:23 ed209 ist offline E-Mail an ed209 senden Beiträge von ed209 suchen Nehmen Sie ed209 in Ihre Freundesliste auf
foogi
Jungspund


Dabei seit: 06.01.2007
Beiträge: 19

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

hallo,

und wie könnte das konkret aussehen?
verwirrt
10.01.2007 22:33 foogi ist offline E-Mail an foogi senden Beiträge von foogi suchen Nehmen Sie foogi in Ihre Freundesliste auf
ed209
Routinier


Dabei seit: 07.09.2006
Beiträge: 308

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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]
12.01.2007 21:02 ed209 ist offline E-Mail an ed209 senden Beiträge von ed209 suchen Nehmen Sie ed209 in Ihre Freundesliste auf
foogi
Jungspund


Dabei seit: 06.01.2007
Beiträge: 19

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
15.01.2007 15:26 foogi ist offline E-Mail an foogi senden Beiträge von foogi suchen Nehmen Sie foogi in Ihre Freundesliste auf
ggg
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

nega
14.12.2018 12:52
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Eine kontextfreie Grammatik für eine Sprache