Kontextfreie Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:05 Di 31.12.2013 | | Autor: | felixf |
Moin DrRiese!
> Zeigen Sie, dass es zu jeder kontextfreien Grammatik G =
> (V, [mm]\Sigma[/mm] , P, S) mit [mm]\epsilon \not\in[/mm] L(G) eine
> äquivalente Grammatik G' gibt, in der alle Regeln von der
> Form
>
> A [mm]\rightarrow[/mm] v mit |v| [mm]\le[/mm] 2
>
> für A [mm]\in[/mm] V und v [mm]\in (\Sigma \cup V)^{+}[/mm] sind.
Also das $V$ aus der letzten Zeile soll vermutlich nicht das gleiche $V$ wie das aus $G$ sein?
> Hänge leider bei dieser Aufgabe total. Ich weiss
> überhaupt gar nicht, wie ich diese Aufgabe angehen soll.
> Hat jemand vllt einen Tipp, der mich in die richtige
> Richtung schubst? 
In $G$ selber hat man ja Regeln der Vorm $A [mm] \rightarrow [/mm] v$, wobei $A$ und $v$ die gleichen Voraussetzungen erfuellen bis auf $|v| [mm] \le [/mm] 2$.
Um dir jetzt einen Hinweis zu geben: wenn du sagen wir eine Regel $A [mm] \to [/mm] b c d e$ hast, kannst du diese ja umschreiben als $A [mm] \to T_1 T_2$, $T_1 \to [/mm] b c$, [mm] $T_2 \to [/mm] d e$ mit [mm] $T_1, T_2$ [/mm] zwei neuen Symbolen, die bisher nicht in $V$ und [mm] $\Sigma$ [/mm] vorgekommen sind.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:26 Do 02.01.2014 | | Autor: | DrRiese |
Hi, danke für die Antwort
Kann ich nicht genau sagen, aber ich denke mal, dass das V für G' ein anderes V sein könnte. Steht leider kein Hinweis dazu..
Ok, ich versuch es mal zu beschreiben:
Es gelte für Grammatik G: A [mm] \rightarrow [/mm] v, |v|=n, n [mm] \in \IN
[/mm]
Dann könnte diese Vorschrift mit [mm] w_{i} \in \Sigma [/mm] folgendermaßen umgeschrieben werden:
A [mm] \rightarrow T_{1}T_{2}
[/mm]
[mm] T_{1} \rightarrow T_{3}T_{4}
[/mm]
[mm] T_{2} \rightarrow T_{5}T_{6}
[/mm]
[mm] T_{3} \rightarrow T_{7}T_{8}
[/mm]
[mm] T_{4} \rightarrow T_{9}T_{10}
[/mm]
[mm] T_{5} \rightarrow T_{11}T_{12}
[/mm]
[mm] T_{6} \rightarrow T_{13}T_{14}
[/mm]
[mm] \vdots
[/mm]
Abbruch, wenn folgende Ableitung möglich:
[mm] T_{i} \rightarrow w_{i}, [/mm] mit [mm] |w_{i}| \le [/mm] 2, [mm] \bigcup w_{i} [/mm] = v, für i [mm] \in [2^{k}-1, 2^{k+1}-2], [/mm] k [mm] \in \IN
[/mm]
Bitte Nachsicht, habe noch nie einen Algorithmus in der Art geschrieben
Wäre das so halbwegs ok?
LG,
DrRiese
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:47 Do 02.01.2014 | | Autor: | felixf |
Moin!
> Ok, ich versuch es mal zu beschreiben:
>
> Es gelte für Grammatik G: A [mm]\rightarrow[/mm] v, |v|=n, n [mm]\in \IN[/mm]
>
> Dann könnte diese Vorschrift mit [mm]w_{i} \in \Sigma[/mm]
> folgendermaßen umgeschrieben werden:
>
> A [mm]\rightarrow T_{1}T_{2}[/mm]
>
> [mm]T_{1} \rightarrow T_{3}T_{4}[/mm]
> [mm]T_{2} \rightarrow T_{5}T_{6}[/mm]
>
> [mm]T_{3} \rightarrow T_{7}T_{8}[/mm]
> [mm]T_{4} \rightarrow T_{9}T_{10}[/mm]
>
> [mm]T_{5} \rightarrow T_{11}T_{12}[/mm]
> [mm]T_{6} \rightarrow T_{13}T_{14}[/mm]
>
> [mm]\vdots[/mm]
>
> Abbruch, wenn folgende Ableitung möglich:
>
> [mm]T_{i} \rightarrow w_{i},[/mm] mit [mm]|w_{i}| \le[/mm] 2, [mm]\bigcup w_{i}[/mm] =
> v, für i [mm]\in [2^{k}-1, 2^{k+1}-2],[/mm] k [mm]\in \IN[/mm]
Sieht etwas kompliziert aus 
Du kannst es noch wesentlich einfacher machen. Und zwar so dass du bei einer Ausgangsregel $A [mm] \to v_1 v_2 \cdots v_n$ [/mm] sofort $n - 1$ Regeln hinschreiben kannst.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 09:16 Fr 03.01.2014 | | Autor: | DrRiese |
Hallo
Ok, versuche ich das ein wenig zu ändern....
Es gelte: v = [mm] v_{1}v_{2}***v_{n}, [/mm] mit [mm] |v_{i}| \le [/mm] 2, i [mm] \in [/mm] [1,...,n].
Dann kann folgende Grammatik aufgestellt werden:
Regel [mm] 1=\begin{cases} A \rightarrow T_{1}T_{2} \end{cases}
[/mm]
Regel [mm] 2=\begin{cases} T_{1} \rightarrow T_{3}T_{4} \\ T_{2} \rightarrow T_{5}T_{6} \end{cases}
[/mm]
Regel [mm] 3=\begin{cases} T_{3} \rightarrow T_{7}T_{8} \\ T_{4} \rightarrow T_{9}T_{10} \\ T_{5} \rightarrow T_{11}T_{12} \\ T_{6} \rightarrow T_{13}T_{14} \end{cases}
[/mm]
[mm] \vdots
[/mm]
Regel n-1 [mm] =\begin{cases} T_{i} \rightarrow v_{j}, & \mbox{für } i \in [2^{n-1}-1,2^{n}-2], j \in [1,...,n] \end{cases}
[/mm]
Meintest du das in etwa so?
LG,
DrRiese
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 So 05.01.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:38 So 05.01.2014 | | Autor: | felixf |
Moin,
sorry, da hab ich wohl vergessen rechtzeitig zu antworten...
> Ok, versuche ich das ein wenig zu ändern....
>
> Es gelte: v = [mm]v_{1}v_{2}***v_{n},[/mm] mit [mm]|v_{i}| \le[/mm] 2, i [mm]\in[/mm]
> [1,...,n].
>
> Dann kann folgende Grammatik aufgestellt werden:
>
> Regel [mm]1=\begin{cases} A \rightarrow T_{1}T_{2} \end{cases}[/mm]
>
> Regel [mm]2=\begin{cases} T_{1} \rightarrow T_{3}T_{4} \\ T_{2} \rightarrow T_{5}T_{6} \end{cases}[/mm]
>
> Regel [mm]3=\begin{cases} T_{3} \rightarrow T_{7}T_{8} \\ T_{4} \rightarrow T_{9}T_{10} \\ T_{5} \rightarrow T_{11}T_{12} \\ T_{6} \rightarrow T_{13}T_{14} \end{cases}[/mm]
>
> [mm]\vdots[/mm]
>
> Regel n-1 [mm]=\begin{cases} T_{i} \rightarrow v_{j}, & \mbox{für } i \in [2^{n-1}-1,2^{n}-2], j \in [1,...,n] \end{cases}[/mm]
>
> Meintest du das in etwa so?
Nein, noch viel einfacher. Wenn du etwa $A [mm] \to v_1 v_2 v_3$ [/mm] hast, mach doch $A [mm] \to v_1 T_1$, $T_1 \to v_2 T_2$, $T_2 \to v_3$. [/mm] Das ist viel einfacher aufzuschreiben.
LG Felix
|
|
|
|
