Chomsky Hiearchie < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:52 Sa 26.10.2013 | | Autor: | tunahan |
| Aufgabe | Entwickeln Sie Grammatiken vom angegebenen Typ zur Erzeugung der folgenden
Sprachen uber [mm] \summe [/mm] = {a,b}
a) Typ [mm] 1:{a^{2}^{k} | k \geq | 1} [/mm] |
Ich hab das versucht leider das ist nur Typ 0 Grammatik
aber ich brauche Typ 1 :(
Grammatik:
G = <{S0, S1, S2, S3, S4, S5}, {a,b}, P, S0>
mit:
P : S0 -> S1S2aS3
S2a-> aaS2
S2S3-> S4S3b | S5
aS4-> S4a
S1S4-> S1S2
aS5-> S5a
S1S5-> €
Ich bedanke mich..
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:47 So 27.10.2013 | | Autor: | tobit09 |
Hallo tunahan!
> Entwickeln Sie Grammatiken vom angegebenen Typ zur
> Erzeugung der folgenden
> Sprachen uber [mm]\summe[/mm] = {a,b}
> a) Typ [mm]1:{a^{2}^{k} | k \geq | 1}[/mm]
> Ich hab das versucht
> leider das ist nur Typ 0 Grammatik
> aber ich brauche Typ 1 :(
> Grammatik:
> G = <{S0, S1, S2, S3, S4, S5}, {a,b}, P, S0>
> mit:
> P : S0 -> S1S2aS3
> S2a-> aaS2
> S2S3-> S4S3b | S5
> aS4-> S4a
> S1S4-> S1S2
> aS5-> S5a
> S1S5-> €
![[notok]](/images/smileys/notok.gif "[notok]") Es gilt [mm] $L(G)=\{aa\}$.
[/mm]
Du denkst VIEL zu kompliziert.
Die Sprache aus der Aufgabenstellung ist sogar regulär und für eine reguläre Grammatik reichen 2 Nichtterminalsymbole völlig aus.
(Wie habt ihr Typ-1-Grammatiken genau definiert?)
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 07:29 So 27.10.2013 | | Autor: | tunahan |
Hallo Tobias danke für die Feedback,
Schuldigung unser Sprache sollte eigentlich [mm] a^{{2}^{k}} [/mm] sein,
Definition vom Typ 1 Sprachen :
(kontextsensitiv) Für jede Produktion [mm] \alpha_{1}\rightarrow \alpha_{2}
[/mm]
[mm] \in [/mm] P gilt:
[mm] \|\alpha_{1}\| \leq \|\alpha_{2}\| [/mm] oder [mm] \alpha_{1} [/mm] = S [mm] \wedge \alpha_{2} [/mm] = [mm] \epsilon [/mm] und falls S [mm] \rightarrow \epsilon \in [/mm] P, darf S auf keiner rechten Regelseite einer Produktion vorkommen.
Hoffe Ihr könnt mir weiterhelfen
viele Grüsse,
Tunahan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:19 So 27.10.2013 | | Autor: | tobit09 |
> Schuldigung unser Sprache sollte eigentlich [mm]a^{{2}^{k}}[/mm]
> sein,
OK, dann ist es natürlich schon ein wenig komplizierter.
> Definition vom Typ 1 Sprachen :
> (kontextsensitiv) Für jede Produktion
> [mm]\alpha_{1}\rightarrow \alpha_{2}[/mm]
> [mm]\in[/mm] P gilt:
> [mm]\|\alpha_{1}\| \leq \|\alpha_{2}\|[/mm] oder [mm]\alpha_{1}[/mm] = S
> [mm]\wedge \alpha_{2}[/mm] = [mm]\epsilon[/mm] und falls S [mm]\rightarrow \epsilon \in[/mm]
> P, darf S auf keiner rechten Regelseite einer Produktion
> vorkommen.
Danke.
Eine Möglichkeit für eine Typ0-Grammatik:
Grundidee für die Ableitung von [mm] $a^{2^k}$ [/mm] ist die $k-1$-fache Verdopplung der $a's$ in $aa$.
Wir gestalten die Grammatik so, dass eine Ableitung eines Wortes von Terminalen aus dem Startsymbol [mm]S_0[/mm] stets in folgender Abfolge erfolgt:
1. Ableitung eines Wortes der Form [mm]S_1^{k-1}aaS_2^{k-1}[/mm] für ein [mm]k\ge 1[/mm].
2. Jedes [mm]S_1[/mm] wandert nach rechts und verdoppelt dabei die [mm]a[/mm]'s, bis ein Teilwort [mm]S_1S_2[/mm] entsteht. Dieses Teilwort wird dann zu [mm]\epsilon[/mm] abgeleitet.
Wir erhalten so das Wort [mm] $a^{2^k}$.
[/mm]
Kriegst du eine solche Grammatik für die gegebene Sprache entworfen?
Um nun eine Typ-1 Grammatik zu erhalten, ersetzen wir die Regel [mm]S_1S_2\rightarrow \varepsilon[/mm] durch [mm]S_1aaS_2\rightarrow aaaa[/mm], so dass wir die Ableitung [mm]S_1aaS_2\rightarrow aaS_1aS_2\rightarrow aaaaS_1S_2\rightarrow aaaa[/mm] ersetzen können durch direkte Anwendung der neuen Regel [mm]S_1aaS_2\rightarrow aaaa[/mm].
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:47 So 27.10.2013 | | Autor: | tunahan |
Hallo Tobit,
Danke aber und wie kriegen wir mit deinem Method den "aa" welche [mm] a^{{2}^{1}} [/mm] ist?
LG Tunahan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:30 So 27.10.2013 | | Autor: | tobit09 |
> Danke aber und wie kriegen wir mit deinem Method den "aa"
> welche [mm]a^{{2}^{1}}[/mm] ist?
Ja.
Leite [mm]S_1^{1-1}aaS_2^{1-1}[/mm] aus [mm]S_0[/mm] ab.
Es gilt schon
[mm]S_1^{1-1}aaS_2^{1-1}=S_1^0aaS_2^0=\epsilon aa\epsilon=aa[/mm].
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:40 So 27.10.2013 | | Autor: | tunahan |
Hallo Tobit,
Sorry ich konnte nicht verstehen was du genau meinst
> Ja.
>
> Leite [mm]S_1^{1-1}aaS_2^{1-1}[/mm] aus [mm]S_0[/mm] ab.
> Es gilt schon
>
> [mm]S_1^{1-1}aaS_2^{1-1}=S_1^0aaS_2^0=\epsilon aa\epsilon=aa[/mm].
soweit ich weiss wir dürfen keine [mm] \epsilon [/mm] benutzen,
vllt wenn du dein ganze Grammatik hier posten kannst konnte ich besser nachvollziehen,
viele Grüsse,
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:48 So 27.10.2013 | | Autor: | tobit09 |
> > Leite [mm]S_1^{1-1}aaS_2^{1-1}[/mm] aus [mm]S_0[/mm] ab.
> > Es gilt schon
> >
> > [mm]S_1^{1-1}aaS_2^{1-1}=S_1^0aaS_2^0=\epsilon aa\epsilon=aa[/mm].
>
> soweit ich weiss wir dürfen keine [mm]\epsilon[/mm] benutzen,
Nicht als rechte Seite von Produktionen einer Typ 1-Grammatik, ja.
Das hatte ich aber auch nicht vor.
> vllt wenn du dein ganze Grammatik hier posten kannst
> konnte ich besser nachvollziehen,
OK, ich gebe die Produktionsregeln meiner Typ 1-Grammatik an:
[mm]S_0\rightarrow S_1S_0S_2|aa[/mm]
[mm]S_1a\rightarrow aaS_1[/mm]
[mm]S_1aaS_2\rightarrow aaaa[/mm]
Die Intention ist wie bereits angedeutet, mittels der oberen Regel zunächst [mm]S_1^{k-1}aaS_2^{k-1}[/mm] abzuleiten und dann mit den unteren beiden Regeln mit jedem vorhandenen [mm]S_1[/mm] und [mm]S_2[/mm] die Zahl der [mm]a[/mm]'s zu verdoppeln.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:11 So 27.10.2013 | | Autor: | tunahan |
Hallo Tobit
hab gerade verstanden
=) funktioniert super gut,
vielen Dank
viele Grüsse,
Tunahan
|
|
|
|
