Sprachbeweis < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:25 So 30.04.2006 | | Autor: | Kiki3000 |
| Aufgabe 1 | Gegeben ist die Grammatik G= ({S,A,B,C,D} , {a,b} , P, S) mit
P = {S [mm] \to [/mm] AB,
A [mm] \to [/mm] CC | CCS,
B [mm] \to [/mm] DD,
C [mm] \to [/mm] a,
D [mm] \to [/mm] b}
Von welchem Typ ist die angegebene Grammatik? |
| Aufgabe 2 | | Bestimmen Sie die von G erzeugte Sprache L. |
| Aufgabe 3 | | Beweisen Sie, dass L tatsächlich die von Ihnen angegebene Sprache L erzeugt. |
Hallo ihr Lieben!
Ich muss dieses Semester Theoretische Informatik 1 besuchen & ich komm schon beim 1. Zettel nicht weiter.
Zum 1. und 2. Teil der Aufgabe hab ich ja auch ne Lsg. Und bei 3. nen Ansatz. Vielleicht könnte da mal einer rüber sehen?! Wäre lieb.
Also:
1. Die Grammatik ist eine Typ2-Grammatik. (sie ist kontext-frei und monoton) [hier bin ich mir eigentlich ziemlich sicher...]
2. [mm] L_1={a^{2n} b^{2n} | n \ge 1}
[/mm]
3. " [mm] \supseteq [/mm] " z.z. [mm] L_1 [/mm] = L(G)
Sei zunächst n=1. z.z. [mm] a^2 b^2 \in [/mm] L(G):
S [mm] \Rightarrow [/mm] AB [mm] \Rightarrow [/mm] CCB [mm] \Rightarrow [/mm] CCDD [mm] \Rightarrow [/mm] aCDD [mm] \Rightarrow [/mm] aaDD [mm] \Rightarrow [/mm] aabD [mm] \Rightarrow [/mm] aabb = [mm] a^2 b^2
[/mm]
Sei nun n>1. z.z. [mm] a^{2n} [/mm] b^2n [mm] \in [/mm] L(G)
(S [mm] \Rightarrow [/mm] AB [mm] \Rightarrow [/mm] CCSB) [mm] \Rightarrow^{n-2} C^{2(n-1)} [/mm] S [mm] B^{n-1} \Rightarrow C^{2(n-1)} AB^{n} \Rightarrow C^{2n} B^n \Rightarrow C^{2n} DDB^{n-1} \Rightarrow^{n-1} C^{2n} D^{2n} \Rightarrow^{n} a^{2n} D^{2n} \Rightarrow^{n} a^{2n} b^{2n} \Box
[/mm]
" [mm] \subseteq [/mm] " ??????
Also bei 3. bin ich mir mal gar nicht sicher. Außerdem hab ich nur eine Richtung... Ich wär euch super dankbar, wenn ihr mir den entscheidenden Tipp geben könntet!
Danke schonmal und Vlg
Kiki
|
|
| |
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo und guten Morgen,
Dein Wunsch ist uns Befehl, wir sehen mal drüber. 
> Gegeben ist die Grammatik G= ({S,A,B,C,D} , {a,b} , P, S)
> mit
> P = \{S [mm]\to[/mm] AB,
> A [mm]\to[/mm] CC | CCS,
> B [mm]\to[/mm] DD,
> C [mm]\to[/mm] a,
> D [mm]\to[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
b\}
>
>
>
> Also:
> 1. Die Grammatik ist eine Typ2-Grammatik. (sie ist
> kontext-frei und monoton) [hier bin ich mir eigentlich
> ziemlich sicher...]
>
Einverstanden.
> 2. [mm]L_1={a^{2n} b^{2n} | n \ge 1}[/mm]
>
Hier dann nicht. Kein Wunder, dass Du mit dem Nachweis [mm] L_1\subseteq [/mm] L(G) keine Schwierigkeiten hast - das ist ja auch richtig.
Aber die umgekehrte Inklusion gilt mitnichten. Erst mal intuitiv: Bei [mm] L_1 [/mm] haben der a- und der b-Teil gleiche Laenge. Bei der Grammatik werden aber der
a- und der b- Teil separat erzeugt - d.h es wird erst ein Term
[mm] CC\ldots CC\: DD\ldots [/mm] DD erzeugt (wobei der C- und der D-Teil jeweils gerade Laenge haben, und dann werden die Terminalsymbole a bzw b eingesetzt - jedenfalls
kann man das stets in dieser Reihenfolge machen. Aber es können der C- und der D-Teil nicht ''miteinander kommunizieren, und daher haben sie nicht notw. die gleiche Laenge.
Es gilt
[mm] L(G)=\{a^{2n}b^{2m}\: |\: n,m\in\IN\}
[/mm]
Hier kann man nun den Beweis von [mm] ''\supseteq'' [/mm] formal durch Induktion nach n und m fuehren.
Die Richtung [mm] ''\subseteq'' [/mm] würd ich genau über eine solche Aussage beweisen: Dass man immer zuerst etwas von der Gestalt
[mm] CC\ldots [/mm] CC [mm] \: DD\ldots [/mm] DD
erzeugen kann, also zu jeder Ableitung eine Ableitung zuordnen kann, die zuerst eine solche Zeichenkette erzeugt und daraus dann das Wort über [mm] \Sigma.
[/mm]
Diesen Beweis würd ichdurch Induktion nach der Länge der Ableitung führen.
Viele Gruesse,
Mathias
> 3. " [mm]\supseteq[/mm] " z.z. [mm]L_1[/mm] = L(G)
> Sei zunächst n=1. z.z. [mm]a^2 b^2 \in[/mm] L(G):
> S [mm]\Rightarrow[/mm] AB [mm]\Rightarrow[/mm] CCB [mm]\Rightarrow[/mm] CCDD
> [mm]\Rightarrow[/mm] aCDD [mm]\Rightarrow[/mm] aaDD [mm]\Rightarrow[/mm] aabD
> [mm]\Rightarrow[/mm] aabb = [mm]a^2 b^2[/mm]
>
> Sei nun n>1. z.z. [mm]a^{2n}[/mm] b^2n [mm]\in[/mm] L(G)
> (S [mm]\Rightarrow[/mm] AB [mm]\Rightarrow[/mm] CCSB) [mm]\Rightarrow^{n-2} C^{2(n-1)}[/mm]
> S [mm]B^{n-1} \Rightarrow C^{2(n-1)} AB^{n} \Rightarrow C^{2n} B^n \Rightarrow C^{2n} DDB^{n-1} \Rightarrow^{n-1} C^{2n} D^{2n} \Rightarrow^{n} a^{2n} D^{2n} \Rightarrow^{n} a^{2n} b^{2n} \Box[/mm]
>
> " [mm]\subseteq[/mm] " ??????
>
> Also bei 3. bin ich mir mal gar nicht sicher. Außerdem hab
> ich nur eine Richtung... Ich wär euch super dankbar, wenn
> ihr mir den entscheidenden Tipp geben könntet!
>
> Danke schonmal und Vlg
> Kiki
|
|
|
|
