Sprache aus Grammatik bestimme < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:13 Di 04.12.2012 | | Autor: | ursular |
| Aufgabe | | Bestimmen Sie die Sprache die durch die Grammatik S->aSbS|ε erzeugt wird. |
Hallo,
Ich bin leider nicht so gut in diesem Fach.
Das ist mein Ansatz bisher:
[mm] |w|_{a}=|w|_{b}
[/mm]
[mm] w_{1}=a [/mm] und [mm] w_{|w|}=b
[/mm]
|w|%2=0
Aber irgendwie scheiter ich daran mir das richtig vorzustellen was da eigentlich passiert.
Gibt es dafür eine Herangehensweise?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo ursular,
> Bestimmen Sie die Sprache die durch die Grammatik
> S->aSbS|ε erzeugt wird.
> Hallo,
> Ich bin leider nicht so gut in diesem Fach.
> Das ist mein Ansatz bisher:
> [mm]|w|_{a}=|w|_{b}[/mm]
Stimmt, die Anzahl der a entspricht der Anzahl der b.
> [mm]w_{1}=a[/mm]
Genau, es beginnt immer mit einem a
> und [mm]w_{|w|}=b[/mm]
> |w|%2=0
Was Du damit aussagen willst erschließt sich mir gerade nicht ganz.
> Aber irgendwie scheiter ich daran mir das richtig
> vorzustellen was da eigentlich passiert.
> Gibt es dafür eine Herangehensweise?
Also zuerst würde ich mal einfach einige Wörter mit Hilfe der Grammatik erzeugen. Daraufhin lässt sich öfters schon das "Schema" der Sprache erkennen.
Richtig erkannt hast Du ja schon, dass immer gleich viele a und b vorkommen.
Kommen diese vielleicht immer in einer bestimmten Reihenfolge vor? Außer dass a immer das 1. Zeichen in jedem Wort ist, was du ebenfalls schon erkannt hast.
Als Tipp vielleicht auch noch: die Sprache lässt sich nicht immer rein "formal" bestimmen, also damit meine ich, dass nicht immer so etwas wie L(G) = [mm] (a^nb^n [/mm] | n >0) möglich ist, sondern auch so etwas wie L(G) = {w [mm] \in [/mm] {a,b}^* | x enthält aab als Teilwort oder ......}
BTW "x enthält aab als Teilwort oder ..." war nur ein Beispiel von mir, diese Beschreibung hat mit der von Dir hier gesuchten nichts zu tun  Wichtig ist hier nur zu wissen, dass Du vielleicht eher in diesem Stil versuchst die Sprache zu beschreiben.
Gruß
Anna
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:21 Do 06.12.2012 | | Autor: | ursular |
Hallo Anna-Lyse,
Ich habe mich heute nochmal damit beschäftigt und habe eine weitere Vermutung nur kann ich die Formal nicht richtig aufschreiben.
Die Idee: Wenn ich an irgendeiner stelle im Wort z.B. 3 b's habe müssen diesen irgendwo 3 a's vorangegangen sein.
Ich hab jetzt versucht es so aufzuschreiben, geht das?
w hat die Form [mm] w=x_{1}...x_{|w|} [/mm] und
für alle [mm] w'=x_{1}...x_{i} [/mm] mit i<=|w| gilt, [mm] |w'|_{b}<=|w'|_{a} [/mm]
und [mm] |w|_{a}=|w|_{b}
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:59 Do 06.12.2012 | | Autor: | Anna-Lyse |
Hallo ursula,
> Die Idee: Wenn ich an irgendeiner stelle im Wort z.B. 3 b's
> habe müssen diesen irgendwo 3 a's vorangegangen sein.
Kannst Du das konkretisieren, wie Du das meinst?
> Ich hab jetzt versucht es so aufzuschreiben, geht das?
> w hat die Form [mm]w=x_{1}...x_{|w|}[/mm] und
> für alle [mm]w'=x_{1}...x_{i}[/mm] mit i<=|w| gilt,
> [mm]|w'|_{b}<=|w'|_{a}[/mm]
> und [mm]|w|_{a}=|w|_{b}[/mm]
>
Hm, sollt Ihr das so formalisiert darstellen?
Davon ab sagst Du ja im Grunde nur, dass die Wörter (und deren Teilwörter) der Sprache höchstens gleich viele b haben als a. Du weißt doch aber noch mehr über die Wörter (z.B. dass sie immer mit a beginnen).
Überlege mal, ob die a und b irgendeinem System folgen, wann sie denn kommen...
Gruß
Anna
PS: Solltest Du weitere Fragen haben (wie in diesem Post z.B.), dann solltest Du Deine Antwort statt in einer Mitteilung besser in einer Frage stellen - die übersieht man nicht so. Denn Mitteilung = Reaktion unnötig.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:33 Sa 08.12.2012 | | Autor: | ursular |
Hallo Anna-Lyse,
Ich dachte es wäre einfacher zu beweisen wenn ich das so formal aufschreibe. So wie ich mir die Beschreibung gedacht habe fängt die Sprache auch mit einem a an und hört mit b auf.
Also wenn wir z.B. das Wort w=ba haben, würde es nicht zu Sprache gehören da für das Teilwort [mm] w'=x_{1} [/mm] die Bedingung [mm] |w'|_{a}>=|w'|_{b} [/mm] schon nicht erfüllt ist.
Wichtig war mir dass nicht mehr b's als vorangegangene a's im Wort auftauchen. Das habe ich mit meinem letzten Post versucht zu sagen.
|
|
|
|
