Mengencharakterisierung < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:23 Fr 12.09.2008 | | Autor: | paimei |
| Aufgabe | Geben sie die Mengencharakterisierung für die Sprache auf dem Alphabet [mm] \summe [/mm] = {a, b} an, die durch folgende Grammatik G = {V, [mm] \Summe, [/mm] P, S} und mit V = {A, S} und folgenden Produktionsregeln erzeugt wird:
S [mm] \to [/mm] bS | abA
A [mm] \to \varepsilon [/mm] | aA | bS |
Jedes Wort beginnt mit [mm] "b^n" [/mm] wobei n auch 0 sein kann, danach muss ein "ab" folgen. Dann kann ich beliebig oft "a" hinzufügen. Nun habe ich aber ein Problem mit der Regel A [mm] \to [/mm] bS. Ich kann hier ja unendlich oft von vorne anfangen. Wie drücke ich so etwas in der Mengenschreibweise aus? Habe mir schon überlegt alles in Klammern zu setzen und diese dann hoch m zu nehmen, das geht ja aber nicht, da die Anzahl der verschiedenen Elemente des Alphabets ja beliebig ist und nicht in jeder Klammer gleich.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Danke im Vorraus.
Gruß Paimei
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:32 Fr 12.09.2008 | | Autor: | Boki87 |
Du lernst wohl für die Info Prüfung an der Uni Stuttgart :)
Also ich habs so gemacht:
[mm] L:\{(b^{n}(ab)^{l}a^{m})(bb^{n}(ab)^{l}a^{m})^{k}|n\ge1,l\ge1,m\ge0,k\ge0\}
[/mm]
Du siehst ja das zunächst b beliebig oft kommen kann, dann kommt auf jeden fall ein ab....es können aber noch mehr ab's kommen denn du hast A->aA und das A kann werden zu A->bS werden, dann hättest wieder ein ab und so weiter...also können beliebig viele ab's kommen.
Da [mm] A->\varepsilon [/mm] muss a gar nicht vorkommen, daher [mm] m\ge0.
[/mm]
Das ganze kann sich jetzt beliebig oft wiederholen, wobei noch ein b mehr drinnen ist wenns sich wiederholt. Daher das ganze nochmal hoch k...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:52 Sa 13.09.2008 | | Autor: | paimei |
Ja genau ^^
Habe aber mittlerweile die Lösung der Aufgabe und deine ist falsch.... ;D
Es kann ja zum Beispiel beliebig viele "b" geben, dass heißt in der ersten Klammer darf nicht die gleiche Hochzahl stehen wie in der 2. Klammer. Hier benötigt man indizierte Hochzahlen. Die Lösung lautet dann:
[mm] $\{(b^{n_i} ab a^{m_i})^i | n_i \ge 0, m_i \ge 0, i > 0\}$
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:32 Sa 13.09.2008 | | Autor: | Boki87 |
Ja aber deins stimmt doch auch nicht...bei dir kann ja nach dem ab kein ab oder b mehr kommen...und das ist ja nicht so...oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:54 Sa 13.09.2008 | | Autor: | paimei |
doch dann ist in der nächsten klammer die hochzahl von b halt 0....
dann hast 2 abs hintereinander....
|
|
|
|
