Informatiker Board | Druckvorschau: kontextfreie Grammatik-Addition/Subtraction

Geschrieben von Alice am 15.01.2011 um 02:04:

kontextfreie Grammatik-Addition/Subtraction

Meine Frage:
Guten Abend!
Ich versuche gerade kontextfreie Grammatiken zu verstehen, bin aber noch nciht hinters System gekommen. Wie handelt man bei Subtraktionen und Additionen in der Hochzahl?
Z.B:
a^n b^m c^(n-m)
a^n b^m c^(n+m)
Also was ist hier die Produktionsregel und wie finde ich sie heraus?
Wäre toll, wenn mir jemand weiterhelfen könnte ;-)

Meine Ideen:
Habe leider noch keine eigene Ansätze, weil Grundverständnis fehlt :-(

Geschrieben von Ibn Batuta am 16.01.2011 um 19:26:

Als Voraussetzung fehlt noch, dass n > m ist.
Sei z.B. n = 5 und m = 2.

Dann hast du im Fall a) a^n b^m c^(n-m) folgendes Wort:
aaaaabbccc

Dann hast du im Fall b) a^n b^m c^(n+m) folgendes Wort:
aaaaabbccccccc

Ibn Batuta

Geschrieben von Alice am 17.01.2011 um 19:32:

Danke für die Antwort!

Wie würde das ganze denn in der S-->aS1B... Schreibweise aussehen? Irgendwie muss es ja auch da möglich sein dem ganzen zu sagen, dass er genau so viele cs haben muss...

Geschrieben von Monarch am 26.01.2011 um 22:49:

hier ma daaaaaaaaaaa lösung:

$[latex]G_{1} = (V, E, P, S) V = \{ S_{1}, S_{2}, S_{3} \} E = \{ a, b, c \} P = \{ S -> S_{1}S_{2}, S_{1} -> acS_{1}, S_{1} -> \epsilon, S_{2} -> baS_{2}, S_{2} -> \epsilon \} S = \{ S \}[/latex]$

Die zweite kriegst du jetzt denke ich schon selber hin, oder?