Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
Drys@k
Anmeldungsdatum: 13.05.2006 Beiträge: 5
|
Verfasst am: 01. Jun 2006 19:14 Titel: Grammatik für kontextfreie Sprache |
|
|
Hallo Leute,
ich möchte zur Sparache L1 welche kontextfrei ist ein geeignete Grammatik finden !
L1 := {a^m b^n | m, n >= 0, m ungleich n}
Dabei macht mir das m ungleich n ziemlich zu schaffen, weil mir nicht ganz klar ist, wie ich eine Produktion P erstellen kann, die beliebig viela a´s und b´s erzeugen kann ohne das entweder das a oder b immer öfter vorkommt als das andere. Da müsste ja iregend was zufälliges in der Produktion geschehen...
Würde mich über einen Denkanstoß sehr freuen..
bzw. vielleicht ist es ja ok die Produktion P so zu wählen das meinetwegen die a´s immer öfter vorkommen wie die b´s oder umgekehrt !!????
MfG
Drys@K |
|
Nach oben |
|
|
|
Crotaphytus
Anmeldungsdatum: 08.05.2005 Beiträge: 213
|
Verfasst am: 01. Jun 2006 19:25 Titel: |
|
|
Hm... Ich weiß jetzt grad überhaupt nicht, wie ich dir da auf die Lösung helfen soll. Von daher schreib ich einfach mal was hin und du sagst mir, was du davon hältst...
s -> axyb
x -> ax
y -> by
x -> _ (leeres Wort)
y -> _
Müsste man eventuell noch an eure Definition von ner kontextfreien Grammatik anpassen und noch noch die Mengen der Variablen und der Terminale definieren. Aber prinzipiell sollts das gewesen sein... _________________ Genie oder Wahnsinn? Wer kann es wissen... |
|
Nach oben |
|
|
Drys@k
Anmeldungsdatum: 13.05.2006 Beiträge: 5
|
Verfasst am: 01. Jun 2006 19:54 Titel: |
|
|
Hallo Crotaphytus,
erstmal Danke für Deine schnelle Antwort.
Unter der Annahme, dass bei Deiner Produktion X und Y Variablen sind bzw. a und b Terminalsymbolde erzeugt Deine Grammatik das Wort a^2 b^2 und nicht das Wort a^m b^n bzw. kommen a´s und b´s bei Dir gleich oft vor welches gegen die Bedingung verstößt, dass es entweder mehr a´s als b´s geben darf oder umgekehrt.
MfG
Drys@k |
|
Nach oben |
|
|
Crotaphytus
Anmeldungsdatum: 08.05.2005 Beiträge: 213
|
Verfasst am: 01. Jun 2006 21:44 Titel: |
|
|
Ja, x und y sind Variablen, a und b Terminale. Und sie erzeugt alles, was du haben willst. Beispiel gefällig? Nehmen wir mal aaab. Also, wir starten bei s (ich hab die Regeln dann auch einfach mal von oben nach unten durchnummeriert, damit du weißt, welche Regel ich anwende):
(1) s -> axyb
(2) -> aaxyb
(2) -> aaaxyb
(4) -> aaayb
(5) -> aaab
Fertig! _________________ Genie oder Wahnsinn? Wer kann es wissen... |
|
Nach oben |
|
|
Drys@k
Anmeldungsdatum: 13.05.2006 Beiträge: 5
|
Verfasst am: 01. Jun 2006 22:23 Titel: re.. |
|
|
OK du hast vollkomen recht...
Danke
Drys@k |
|
Nach oben |
|
|
|