Informatiker Board | Theoretische Informatik | kontextfreie Grammatik-Addition/Subtraction

Informatiker Board » Themengebiete » Theoretische Informatik » kontextfreie Grammatik-Addition/Subtraction

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

kontextfreie Grammatik-Addition/Subtraction

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Alice
Grünschnabel

Dabei seit: 15.01.2011
Beiträge: 2

kontextfreie Grammatik-Addition/Subtraction

Zitatantwort auf diesen Beitrag erstellen

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 :-(

15.01.2011 02:04

Nehmen Sie Alice in Ihre Freundesliste auf

Ibn Batuta Ibn Batuta ist männlich

Mitglied

Dabei seit: 02.01.2011
Beiträge: 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

16.01.2011 19:26

Nehmen Sie Ibn Batuta in Ihre Freundesliste auf

Alice
Grünschnabel

Dabei seit: 15.01.2011
Beiträge: 2

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...

17.01.2011 19:32

Monarch
unregistriert

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?

26.01.2011 22:49

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » kontextfreie Grammatik-Addition/Subtraction