Kontextfreie Grammatiken < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 21:14 So 30.01.2005 | | Autor: | Ronntze |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich habe in Informatik eine Aufgabe bekommen, mit der ich überhaupt nichts anfangen kann.
Kann mir vielleicht jemand helfen?
Geben Sie kontextfreie Grammatiken [mm] G_{1}, G_{2}, G_{3} [/mm] an, für die jeweils gilt:
a) [mm] L(G_{1})= \{w |w= a^{n}b^{3n},n \ge0 \}
[/mm]
b) [mm] L(G_{2})= \{w |w= a^{2n}b^{2n},n \ge1 \}
[/mm]
c) [mm] L(G_{3})= \{w |w \in\{a,b\}^{\*},|w|=3n,n\ge1\}
[/mm]
Achten Sie auf korrekte formale Notation und Schreibweise.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:32 So 30.01.2005 | | Autor: | Bastiane |
Hallo Ronntze !
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Ich habe in Informatik eine Aufgabe bekommen, mit der ich
> überhaupt nichts anfangen kann.
> Kann mir vielleicht jemand helfen?
>
> Geben Sie kontextfreie Grammatiken [mm]G_{1}, G_{2}, G_{3}[/mm] an,
> für die jeweils gilt:
>
> a) [mm]L(G_{1})= \{w |w= a^{n}b^{3n},n \ge0 \}
[/mm]
>
> b) [mm]L(G_{2})= \{w |w= a^{2n}b^{2n},n \ge1 \}
[/mm]
>
> c) [mm]L(G_{3})= \{w |w \in\{a,b\}^{\*},|w|=3n,n\ge1\}
[/mm]
>
>
> Achten Sie auf korrekte formale Notation und
> Schreibweise.
Also erstmal hast du vielleicht noch nicht bemerkt, dass wir auch ein kleines Informatikforum haben. Da wäre die Frage wohl besser aufgehoben... Und dann lies dir bitte mal unsere Forenregeln durch. Warum kannst du denn mit dieser Aufgabe nichts anfangen? Du sollst halt eine Grammatik für die Sprachen da oben angeben. Das ist nicht immer ganz einfach, aber ausprobieren kann man da doch immer!
Wie wär's mal mit einem Ansatz deinerseits?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:45 So 30.01.2005 | | Autor: | Ronntze |
Tut mir leid, daß ich im falschen Forum gelandet bin. Aber ich bin heute neu auf diese Seite gestoßen, und habe nicht gewusst, daß es auch ein Informatik-Forum gibt.
Aber danke für die Info.
Kann man diese Aufgabe aber nicht vielleicht trotzdem ins Matheforum stellen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:29 Di 01.02.2005 | | Autor: | Karl_Pech |
Hallo,
Du hast bis jetzt noch keinen Lösungsvorschlag gepostet, weshalb ich davon ausgehe, daß Du die Lösung entweder schon hast oder bereits resigniert hast. Ich gehe mal vom Letzteren aus und löse dir mal die Aufgaben 1 und 3 um dich etwas zu motivieren! 
Aufgabe 1:
> a) [mm]L(G_{1}) = L := \{w |w= a^{n}b^{3n},n \ge0 \}
[/mm]
Diese Aufgabe sollte einfach sein, die Grammatik [m]G_1 = \left( {\left\{ S \right\},\left\{ {a,b} \right\},\left\{ {S \to aSbbb\;|\;\varepsilon\;|\;abbb} \right\},S} \right)[/m] sollte die Aufgabe lösen. Sie erzeugt für n = 0 ein leeres Wort, für n = 1 abbb und ansonsten erzeugt sie links eine beliebige Anzahl von a's und gleichzeitig rechts eine dreimal so große Anzahl von b's.
Formal:
[m]\begin{gathered}
n = 0:S \Rightarrow _{G_1 } \varepsilon \hfill \\
n = 1:S \Rightarrow _{G_1 } abbb \hfill \\
n > 1:S \Rightarrow _{G_1 } aSbbb \Rightarrow _{G_1 } aaSbbbbbb \Rightarrow _{G_1 } aaaSbbbbbbbbb \Rightarrow _{G_1 } \ldots \Rightarrow _{G_1 }^ {\star} a^n b^{3n} \hfill \\
\end{gathered}[/m]
Aufgabe 2 geht fast genauso.
Aufgabe 3:
> c) [mm]L(G_{3}) = L := \{w |w \in\{a,b\}^{\star},|w|=3n,n\ge1\}
[/mm]
Diese Aufgabe scheint schon wesentlicher schwerer zu sein. Jedenfalls habe ich nach einigem Probieren keine brauchbare Grammatik rausgekriegt. :-(
Zum Glück beschreiben nicht nur kontextfreie Grammatiken Typ-2 Sprachen. Typ-2 Sprachen werden auch von sogenannten Kellerautomaten beschrieben. Insbesondere sind die nicht-deterministischen Kellerautomaten (NKAs) genauso mächtig wie kontextfreie Grammatiken (bei DKAs sollte man da schon vorsichtig sein, weil sie nicht so mächtig sind, wie NKAs!).
Der Beweis dazu ist kontruktiv und erzeugt aus einem allgemeinen NKA eine kontextfreie Grammatik und umgekehrt. Uns interessiert hier aber der erste Teil des Beweises. Intuitiv ist es (zumindest mir) leichter einen NKA für dieses Problem anzugeben.
Idee:
1.) Der Automat liest das Wort zeichenweise ein und packt für jedes Zeichen ein Stacksymbol auf den Stack. (Beachte: Standardmäßig ist jeder KA so konfiguriert, daß er ein unterstes Kellersymbol hat, denn der Automat akzeptiert ein Wort genau dann, wenn der Keller leer ist, und das Wort komplett eingelesen wurde. Ohne ein solches Symbol müßte es eine Möglichkeit geben Stacksymbole "aus dem Nichts" zu erzeugen. Das wäre aber letztenendes sinnlos, weil ich dann jedes beliebige Wort akzeptieren könnte, indem ich mir die passenden Stacksymbole "einfach so aus dem Nichts holen" könnte. Deshalb gibt es solch' ein Symbol, welches wir ab jetzt mit '#' bezeichnen.)
2.) Hat der Automat das komplette Wort eingelesen, entfernt er seine Stacksymbole in 3er-Päckchen. War das Wort von der Länge 3n bleibt somit nur # im Keller. Zuletzt entfernt er auch # und akzeptiert das Wort.
War das Wort länger oder kürzer, so müßte der Automat im Löschvorgang eines letzten 3er-Päckchens steckenbleiben, weil er alle Stack-Symbole bis auf # entfernt hat, sich aber im "falschen" Zustand befindet, um # zu entfernen, er besitzt auch keine weiteren Übergänge mehr um sich aus diesem Zustand zu "befreien", damit verwirft er das Wort.
Hier ist der Automat (die Schreibweise unten kann man vereinbaren [m]\delta \left( {z,a,A} \right) \mathrel\backepsilon \left( {z',x} \right) \equiv :zaA \to z'x
[/m], sie ist also durchaus formal):
[m]\begin{gathered}
\left. \begin{gathered}
z_0 a\# \to z_1 A\# , \hfill \\
z_0 b\# \to z_1 A\# , \hfill \\
\hfill \\
z_1 aA \to z_1 AA, \hfill \\
z_1 bA \to z_1 AA, \hfill \\
\end{gathered} \right\}\begin{array}{*{20}c}
{{\text{Wort zeichenweise einlesen und}}} \\
{{\text{dabei immer ein }}A{\text{ auf den Stack legen}}} \\
\end{array} \hfill \\
\hfill \\
\left. \begin{gathered}
z_1 \varepsilon A \to z_2 \varepsilon , \hfill \\
z_2 \varepsilon A \to z_3 \varepsilon , \hfill \\
z_3 \varepsilon A \to z_1 \varepsilon \hfill \\
\end{gathered} \right\}\begin{array}{*{20}c}
{{\text{Das komplette Wort wurde eingelesen}}{\text{.}}} \\
{{\text{Wir löschen nun hintereinander jeweils 3 }}A's{\text{.}}} \\
\end{array} \hfill \\
\hfill \\
\left. {z_1 \varepsilon \# \to z_0 \varepsilon } \right\}{\text{Haben wir vorhin ein Wort der Länge 3n gelesen}}{\text{, so löschen wir \# und akzeptieren}}{\text{.}} \hfill \\
\end{gathered}[/m]
Den Beweis, daß der Automat richtig ist, spare ich mir jetzt. Er scheint schon richtig zu sein, und wenn nicht, wird irgendjemand hier im Forum irgendwann schon etwas dazu anmerken.
Bei der Umwandlung zur Grammatik komme ich jetzt nicht weiter.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:06 Mi 02.02.2005 | | Autor: | Lizard |
> > a) [mm]L(G_{1}) = L := \{w |w= a^{n}b^{3n},n \ge0 \}[/mm]
>
> [m]G_1 = \left( {\left\{ S \right\},\left\{ {a,b} \right\},\left\{ {S \to aSbbb\;|\;\varepsilon\;|\;abbb} \right\},S} \right)[/m]
Die Regel nach $abbb$ ist unnötig, da du dieses Wort auch mit $aSbbb$ und [mm] $S\to\epsilon$ [/mm] ableiten kannst.
> > c) [mm]L(G_{3}) = L := \{w |w \in\{a,b\}^{\star},|w|=3n,n\ge1\}[/mm]
>
> Diese Aufgabe scheint schon wesentlicher schwerer zu sein.
Naja: $S [mm] \to aAB_1 [/mm] | [mm] bAB_1$
[/mm]
[mm] $AB_1 \to aAB_2 [/mm] | [mm] bAB_2$
[/mm]
[mm] $AB_2 \to [/mm] aS | bS | a | b$
[mm] $AB_n$ [/mm] ist in diesem Fall ein einzelnes Symbol. Ich würde die Lösung eigentlich ungern so einfach hinschreiben, aber in diesem Fall scheint es wohl nicht mehr zu schaden. Würdest du denn dem Ansatz so zustimmen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:04 Mi 02.02.2005 | | Autor: | Karl_Pech |
> > > a) [mm]L(G_{1}) = L := \{w |w= a^{n}b^{3n},n \ge0 \}[/mm]
> >
>
> > [m]G_1 = \left( {\left\{ S \right\},\left\{ {a,b} \right\},\left\{ {S \to aSbbb\;|\;\varepsilon\;|\;abbb} \right\},S} \right)[/m]
>
>
> Die Regel nach [mm]abbb[/mm] ist unnötig, da du dieses Wort auch mit
> [mm]aSbbb[/mm] und [mm]S\to\epsilon[/mm] ableiten kannst.
Jup, hast Recht! 
> > > c) [mm]L(G_{3}) = L := \{w |w \in\{a,b\}^{\star},|w|=3n,n\ge1\}[/mm]
>
> >
> > Diese Aufgabe scheint schon wesentlicher schwerer zu
> sein.
>
> Naja: [mm]S \to aAB_1 | bAB_1[/mm]
> [mm]AB_1 \to aAB_2 | bAB_2[/mm]
> [mm]AB_2 \to aS | bS | a | b[/mm]
>
>
> [mm]AB_n[/mm] ist in diesem Fall ein einzelnes Symbol. Ich würde die
> Lösung eigentlich ungern so einfach hinschreiben, aber in
> diesem Fall scheint es wohl nicht mehr zu schaden. Würdest
> du denn dem Ansatz so zustimmen?
Ja, die Grammatik leistet tatsächlich das Gewünschte.
Vereinfacht betrachtet ist es das hier:
$S [mm] \rightarrow kA,\;A \rightarrow kB,\;B \rightarrow kS\;|\;k$.
[/mm]
Also z.B. $S [mm] \Rightarrow [/mm] kA [mm] \Rightarrow [/mm] kkB [mm] \Rightarrow [/mm] kkk$
und ansonsten $S [mm] \Rightarrow [/mm] kA [mm] \Rightarrow [/mm] kkB [mm] \Rightarrow [/mm] kkkS$
und es ist klar, daß sich das Ganze jetzt wiederholt.
Im Moment vermute ich sowieso, daß mein Ansatz mit dem Kellerautomaten
nicht richtig war, und daß die Falschheit der Grammatik, die ich da raus hatte von der Falschheit des Automaten herrührte. Vermutlich liegt es daran, daß ein NKA halt nichtdeterministisch ist (wie der Name schon sagt). Ich habe vorrausgesetzt, daß er zuerst das komplette Wort einliest und dann erst die [mm] $\epsilon\text{-\"Uberg\"ange macht.}$ [/mm] Wer garantiert mir eigentlich, daß der NKA nicht irgendwo beim Einlesen des Wortes einen solchen Übergang macht? Dann akzeptiert er jedenfalls auch Wörter der Länge 1, 2, 3, 4, . Wenn ich mich jetzt nicht wieder täusche. Auf alle Fälle ist das wohl der Grund für die fehlerhafte Grammatik.
Die Grammatik, die Du hier angegeben hast, ist in jedem Fall regulär. Das heißt man brauchte gar keinen Kellerautomaten, um das zu lösen. Nur habe ich's leider zu spät bemerkt. :-(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:43 Mi 02.02.2005 | | Autor: | Lizard |
Hallo,
> Ja, die Grammatik leistet tatsächlich das Gewünschte.
>
> Vereinfacht betrachtet ist es das hier:
>
> [mm]S \rightarrow kA,\;A \rightarrow kB,\;B \rightarrow kS\;|\;k[/mm].
>
> Also z.B. [mm]S \Rightarrow kA \Rightarrow kkB \Rightarrow kkk[/mm]
>
> und ansonsten [mm]S \Rightarrow kA \Rightarrow kkB \Rightarrow kkkS[/mm]
>
> und es ist klar, daß sich das Ganze jetzt wiederholt.
Genau, mit $k [mm] \to [/mm] a | b$.
> Im Moment vermute ich sowieso, daß mein Ansatz mit dem
> Kellerautomaten nicht richtig war, und daß die Falschheit der Grammatik,
> die ich da raus hatte von der Falschheit des Automaten
> herrührte.
Kann sein, den hab ich mir ehrlich gesagt nicht angeschaut. Sah mir zu kompliziert aus ;)
> -snip-
> Die Grammatik, die Du hier angegeben hast, ist in jedem
> Fall regulär. Das heißt man brauchte gar keinen
> Kellerautomaten, um das zu lösen. Nur habe ich's leider zu
> spät bemerkt. :-(
Macht ja nichts. Man braucht tatsächlich keinen, und ein einfacher akzeptierender DFA braucht gerade mal 4 Zustände, um die jeweils gelesene Anzahl von a/b mod 3 zu speichern (wenn man $n [mm] \ge [/mm] 0$ erlauben würde, würden auch 3 reichen). Ist also letztlich wirklich nicht so kompliziert :)
|
|
|
|
