Sprache finden < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:15 Fr 10.05.2013 | | Autor: | bandchef |
| Aufgabe | | Zeigen sie mittels vollständiger Induktion für die kontextfreie Grammatik [mm] $G=\{V,\Sigma, P, S\}$, [/mm] mit [mm] $V=\{S\}$ [/mm] und [mm] $P\{S \to 0S1S|1S0S|\epsilon\}$, [/mm] dass L(G) die Menge aller Zeichenfolgen beschreibt, die genauso viel 0en wie 1en enthalten. |
Hi Leute!
Ich verstehe die Aufgabe so, dass ich erst eine Sprache definieren soll, die der kontextfreien Grammatik entspricht. Richtig?
1. Frage: Fehlt in der Angabe dann nicht die Angabe des Alphabets [mm] $\Sigma$? [/mm] Auch auf meinem Blatt ist davon keine Rede.
2. Frage: Ich hab mir nun auf meinem Aufgabenblatt einfach das Alphabet ergänzt: [mm] $\Sigma [/mm] = [mm] \{0,1\}$ [/mm] Richtig?
Des Weiteren hab ich auch schon mal angefangen eine Sprache zu entwerfen:
$L(G) = [mm] \{0^n 1^n | n \in \mathbb N\}$
[/mm]
Diese Sprache generiert mir zwar genauso viel 0en wie 1en es fehlt aber die Eigenschaft, dass die 0en und 1en auch wild durcheinander angeordnet stehen können...; wie bringe ich das in die Sprache L(G) rein?
Ein großes Fragezeichen wirft dann aber auch noch vollständige Induktion der Sprache auf. Wie macht man das dann?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:37 Sa 11.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
> 1. Frage: Fehlt in der Angabe dann nicht die Angabe des
> Alphabets [mm]\Sigma[/mm]? Auch auf meinem Blatt ist davon keine
> Rede.
>
> 2. Frage: Ich hab mir nun auf meinem Aufgabenblatt einfach
> das Alphabet ergänzt: [mm]\Sigma = \{0,1\}[/mm] Richtig?
Ja, ich denke das wurde schlicht vergessen und ist so gemeint.
> Ich verstehe die Aufgabe so, dass ich erst eine Sprache
> definieren soll, die der kontextfreien Grammatik
> entspricht. Richtig?
>
>
> Des Weiteren hab ich auch schon mal angefangen eine Sprache
> zu entwerfen:
>
> [mm]L(G) = \{0^n 1^n | n \in \mathbb N\}[/mm]
>
> Diese Sprache generiert mir zwar genauso viel 0en wie 1en
> es fehlt aber die Eigenschaft, dass die 0en und 1en auch
> wild durcheinander angeordnet stehen können...; wie bringe
> ich das in die Sprache L(G) rein?
$L(G)$ ist ja schon definiert: In der Vorlesung habt ihr sicherlich zu jeder Grammatik $G$ die zugehörige Sprache $L(G)$ definiert.
Aber du könntest die Sprache, von der wir behaupten (aber noch nicht wissen), dass sie mit $L(G)$ übereinstimmt, z.B. $L$ nennen:
[mm] $L:=\{w\in\{0,1\}^\star\;|\;w\text{ enthält genauso viele 1en wie 0en}\}$.
[/mm]
Die Behauptung ist also nun: $L(G)=L$.
> Ein großes Fragezeichen wirft dann aber auch noch
> vollständige Induktion der Sprache auf. Wie macht man das
> dann?
Da $L(G)$ und $L$ Sprachen, also Mengen von Wörtern sind, ist nacheinander [mm] $L(G)\subseteq [/mm] L$ und [mm] $L(G)\supseteq [/mm] L$ zu zeigen.
(Das kann man sehr formal oder weniger formal machen. Wenn du es sehr formal möchtest, so poste bitte eure genaue Definition von $L(G)$ inklusive der dazu benötigten Hilfsdefinitionen.)
Für [mm] $L(G)\subseteq [/mm] L$ ist zu zeigen, dass [mm] $w\in [/mm] L$ für alle [mm] $w\in [/mm] L(G)$ gilt.
Sei also [mm] $w\in [/mm] L(G)$, d.h. $w$ ist aus $S$ mittels der Produktionen von $G$ ableitbar.
Zu überlegen ist, dass [mm] $w\in [/mm] L(G)$ gilt, also dass $w$ genauso viele 1en wie 0en enthält.
[mm] $L(G)\supseteq [/mm] L$ ist alles andere als einfach einzusehen.
Zu zeigen ist, dass [mm] $w\in [/mm] L(G)$ für alle [mm] $w\in [/mm] L$ gilt.
Hier würde ich eine Induktion nach der Anzahl $n$ der 1en (= Anzahl der 0en) in [mm] $w\in [/mm] L$ durchführen.
D.h. per Induktion zu zeigen: Für alle [mm] $n\in\IN_0$ [/mm] gilt: Alle Wörter $w$ über dem Alphabet [mm] $\{0,1\}$ [/mm] mit genau $n$ 1en und genau $n$ 0en sind mittels der Produktionen von G aus S ableitbar.
Den Induktionsanfang $n=0$ kriegst du sicherlich alleine hin.
Sei nun $n>0$ und $w$ ein Wort über dem Alphabet [mm] $\{0,1\}$ [/mm] mit genau $n$ 1en und genau $n$ 0en. Zu zeigen ist, dass $w$ mittels der Produktionen von G aus S ableitbar ist.
Induktionsvoraussetzung: Für alle $m<n$ gilt: Alle Wörter $v$ über dem Alphabet [mm] $\{0,1\}$ [/mm] mit genau $m$ 1en und genau $m$ 0en sind mittels der Produktionen von G aus S ableitbar.
Um die Induktionsvoraussetzung gewinnbringend nutzen zu können, gilt es, geeignete Wörter $v$ mit genau $m$ 1en und genau $m$ 0en für ein $m<n$ zu betrachten.
Unterscheide nun die Fälle
1. $w$ beginnt mit einer 0 und
2. $w$ beginnt mit einer 1.
Mit welcher Produktionsregel wird man die Ableitung von $w$ aus $S$ in diesen beiden Fällen jeweils beginnen?
Wie man dann die Induktionsvoraussetzung ins Spiel bringen kann, ist alles andere als einfach...
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:24 So 12.05.2013 | | Autor: | bandchef |
Ich hab also nun das auf meinem Blatt stehen:
$L := [mm] \{w \in \{0,1\}^{\*} | \text{w enthält genauso viele 0en wie 1en}\}$
[/mm]
Behauptung: $L(G) = L$
1.) z.z.: $L(G) [mm] \subseteq [/mm] L$
Sei $w [mm] \in [/mm] L(G)$, dann ist w aus S mittels der Produktionen von G ableitbar.
So, und ab jetzt weiß ich auch nicht mehr weiter. Wobei du ja meintest, dass der Fall $L(G) [mm] \subseteq [/mm] L$ noch der einachere von beiden ist, oder?
Muss ich hier jetzt auch eine Induktion machen? Wenn ja, dann muss ich wohl auch erst einen Induktionsanfang machen, oder? Beginnt dieser auch bei n=0? Ich mach dann einfach mal:
(IA):
n=0: $S [mm] \to \epsilon$ [/mm] dann folgen keine 0en, keine 1en
n=1: $S [mm] \to [/mm] 0S1S [mm] \to [/mm] 01S [mm] \to [/mm] 01$ dann folgen eine 1 und eine 0
(IS):
n>1: $S [mm] \to [/mm] 0S1S [mm] \to [/mm] 01S [mm] \to [/mm] 011S0S [mm] \to \underbrace{01100S1S}_{=n-1} \to [/mm] 011001S [mm] \to [/mm] 0110010S1S [mm] \to \underbrace{01100101}_{=n}$
[/mm]
[mm] $\Rightarrow$ [/mm] Es folgen genauso viel 0en wie 1en.
Ehrlich gesagt bin ich mir nicht sicher, ob da so stimmt. Da ich ja bspw. mit der Produktion $S [mm] \to [/mm] 0S1S$ zweimal eine neue Produktion ranhängen kann, weiß ich nicht so genau, ob die gekennzeichneten beiden Schritte (vorletztes und letztes Element) an der richtigen Stelle stehen! Was meinst du?
Jetzt müsste ich ja noch $L(G) [mm] \supseteq [/mm] L$ zeigen. Aber da weiß ich jetzt nicht mehr weiter...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:13 So 12.05.2013 | | Autor: | tobit09 |
> [mm]L := \{w \in \{0,1\}^{\*} | \text{w enthält genauso viele 0en wie 1en}\}[/mm]
>
> Behauptung: [mm]L(G) = L[/mm]
>
> 1.) z.z.: [mm]L(G) \subseteq L[/mm]
>
> Sei [mm]w \in L(G)[/mm], dann ist w aus S mittels der Produktionen
> von G ableitbar.
Das sieht doch schon einmal sehr ordentlich aus!
> So, und ab jetzt weiß ich auch nicht mehr weiter. Wobei du
> ja meintest, dass der Fall [mm]L(G) \subseteq L[/mm] noch der
> einachere von beiden ist, oder?
Ja. Ich sage nicht, dass er einfach ist. Aber die andere Teilmengenbeziehung ist schwierig.
> Muss ich hier jetzt auch eine Induktion machen? Wenn ja,
> dann muss ich wohl auch erst einen Induktionsanfang machen,
> oder? Beginnt dieser auch bei n=0? Ich mach dann einfach
> mal:
Wenn du Induktion verwendest, solltest du auch verraten, welche Aussage über alle natürlichen Zahlen du beweisen möchtest.
Hier wäre ein Beweis folgender Aussage per Induktion sinnvoll:
Für alle natürlichen Zahlen $n$ gilt: Alle Wörter Alphabet [mm] $\{S\}\cup\{0,1\}$, [/mm] die aus $S$ mittels der Produktionen von $G$ in $n$ Schritten ableitbar sind, enthalten genauso viele 1en wie 0en.
Insbesondere enthält dann unser Wort w genauso viele 1en wie 0en.
Induktionsanfang: $n=0$. Welche Wörter über [mm] $\{S\}\cup\{0,1\}$ [/mm] sind aus S in 0 Schritten ableitbar?
Induktionsschritt: [mm] $n\rightarrow [/mm] n+1$
Induktionsvoraussetzung: Alle in $n$ Schritten aus $S$ ableitbaren Wörter über [mm] $S\cup\{0,1\}$ [/mm] enthalten genauso viele 1en wie 0en.
Induktionsbehauptung: Alle in $n+1$ Schritten aus $S$ ableitbaren Wörter über [mm] $S\cup\{0,1\}$ [/mm] enthalten genauso viele 1en wie 0en.
Sei also $v$ ein in $n+1$ Schritten aus $S$ ableitbares Wort über [mm] $S\cup\{0,1\}$ [/mm] und [mm] $S=v_0\to v_1\to\ldots\to v_n\to v_{n+1}=v$ [/mm] eine Ableitung von $v$.
Was weißt du nach Induktionsvoraussetzung über [mm] $v_n$?
[/mm]
Welche Produktionsregeln könnten Grundlage für den Ableitungsschritt [mm] $v_n\to v_{n+1}$ [/mm] sein?
> Jetzt müsste ich ja noch [mm]L(G) \supseteq L[/mm] zeigen. Aber da
> weiß ich jetzt nicht mehr weiter...
Ich habe ja schon einiges dazu geschrieben.
Zu zeigen:
Für alle [mm] $n\in\IN_0$ [/mm] gilt: Alle Wörter $w$ über dem Alphabet [mm] $\{0,1\}$ [/mm] mit genau $n$ 1en und genau $n$ 0en sind mittels der Produktionen von G aus S ableitbar.
Wie sieht das im Spezialfall $n=0$ aus?
Um ein weiteres Gespür für die Aussage zu kriegen, könntest du auch noch die Spezialfälle $n=1$ und $n=2$ betrachten.
Danach:
Unterscheide nun die Fälle
1. $w$ beginnt mit einer 0 und
2. $w$ beginnt mit einer 1.
Mit welcher Produktionsregel wird man die Ableitung von $w$ aus $S$ in diesen beiden Fällen jeweils beginnen?
Woran hakt es bei diesen Punkten? Ich erwarte nicht, dass du den kompletten Beweis hinbekommst. Aber zumindest den Fall $n=0$ traue ich dir zu! 
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:48 Mo 13.05.2013 | | Autor: | bandchef |
[mm]L := \{w \in \{0,1\}^{\*} | \text{w enthält genauso viele 0en wie 1en}\}[/mm]
Behauptung: [mm]L(G) = L[/mm]
1.) z.z.: [mm]L(G) \subseteq L[/mm]
[mm] $\forall n\in \mathbb [/mm] N$ und $ [mm] \forall [/mm] w [mm] \in \{S\}\cup\{0,1\}$, [/mm] die aus S mittels der Produktionen von G in n Schritten ableitbar sind, enthalten genauso viele 0en wie 1en.
(IA)
n=0: ableitbare Wörter [mm] $\{\}$
[/mm]
(IS)
[mm] $n\to [/mm] n+1$:
Induktionsvoraussetzung: Alle in n Schritten aus S ableitbare Wörter über [mm] $\{S\}\cup\{0,1\}$ [/mm] enthalten genauso viele 0en wie 1en.
Induktionsbehauptung: Alle in n+1 Schritten aus S ableitbare Wörter über [mm] $\{S\}\cup\{0,1\}$ [/mm] enthalten genauso viele 0en wie 1en.
Sei also v ein in n+1 Schritten aus S ableitbares Wort über [mm] $\{S\}\cup\{0,1\}$ [/mm] und $S= [mm] v_0 \to v_1 \to ...\to v_n \to v_{n+1} [/mm] = v$ und sei [mm] $(01)^{n+1}$ [/mm] das hier einzige Wort der Länge n+1.
> Was weißt du nach Induktionsvoraussetzung über [mm] $v_n$?
[/mm]
Nach (IV): Im Schritt n erzeugt G das Wort [mm] $(01)^n$ [/mm] und die letzte Ableitung war $S [mm] \to \epsilon$. [/mm] Wir ersetzen $S [mm] \to \epsilon$ [/mm] durch $S [mm] \to [/mm] 01S [mm] \to [/mm] 01$ und erhalten das neue Wort [mm] $01(01)^n [/mm] = [mm] (01)^{n+1}$.
[/mm]
> Welche Produktionsregeln könnten Grundlage für den Ableitungsschritt sein?
Mögliche Produktionsregeln sind: $S [mm] \to [/mm] 0S1S | 1S0S | [mm] \epsilon$
[/mm]
Ich würd jetzt gerne erst den ersten Teilbeweis, also [mm]L(G) \subseteq L[/mm] zeigen, bevor wir mit [mm]L(G) \supseteq L[/mm] weitermachen, ok?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:24 Di 14.05.2013 | | Autor: | tobit09 |
> [mm]L := \{w \in \{0,1\}^{\*} | \text{w enthält genauso viele 0en wie 1en}\}[/mm]
>
> Behauptung: [mm]L(G) = L[/mm]
>
> 1.) z.z.: [mm]L(G) \subseteq L[/mm]
>
Behauptung:
> [mm]\forall n\in \mathbb N[/mm] und [mm]\forall w \in \{S\}\cup\{0,1\}[/mm],
Es müsste [mm] $w\in(\{S\}\cup\{0,1\})^\*$ [/mm] heißen. Es geht ja um Worte w über dem Alphabet [mm] $\{S\}\cup\{0,1\}$, [/mm] nicht etwa Buchstaben dieses Alphabetes.
> die aus S mittels der Produktionen von G in n Schritten
> ableitbar sind, enthalten genauso viele 0en wie 1en.
>
> (IA)
> n=0: ableitbare Wörter [mm]\{\}[/mm]
Das einzige in 0 Schritten aus S ableitbare Wort über [mm] $\{S,0,1\}$ [/mm] ist $S$. Es enthält 0 1en und 0 0en.
> (IS)
> [mm]n\to n+1[/mm]:
>
> Induktionsvoraussetzung: Alle in n Schritten aus S
> ableitbare Wörter über [mm]\{S\}\cup\{0,1\}[/mm] enthalten genauso
> viele 0en wie 1en.
> Induktionsbehauptung: Alle in n+1 Schritten aus S
> ableitbare Wörter über [mm]\{S\}\cup\{0,1\}[/mm] enthalten genauso
> viele 0en wie 1en.
>
> Sei also v ein in n+1 Schritten aus S ableitbares Wort
> über [mm]\{S\}\cup\{0,1\}[/mm] und [mm]S= v_0 \to v_1 \to ...\to v_n \to v_{n+1} = v[/mm]
> und sei [mm](01)^{n+1}[/mm] das hier einzige Wort der Länge n+1.
[mm] $(01)^{n+1}$ [/mm] hat Länge $2*(n+1)$. Es ist sicherlich nicht das einzige Wort dieser Länge.
$n+1$ ist eine Anzahl der Schritte, in denen $v$ aus S ableitbar ist. Warum betrachtest du nun mit [mm] $(01)^{n+1}$ [/mm] ein Wort der Länge $2*(n+1)$?
> > Was weißt du nach Induktionsvoraussetzung über [mm]v_n[/mm]?
>
> Nach (IV): Im Schritt n erzeugt G das Wort [mm](01)^n[/mm]
Das ist eine falsche Aussage und hat nichts mit der Induktionsvoraussetzung zu tun.
> und die
> letzte Ableitung war [mm]S \to \epsilon[/mm].
Du meinst die Ableitung [mm] $v_n\to v_{n+1}$ [/mm] bestand in einer Anwendung der Regel [mm] $S\to\epsilon$? [/mm] Warum das?
> Wir ersetzen [mm]S \to \epsilon[/mm]
> durch [mm]S \to 01S \to 01[/mm]
> und erhalten das neue Wort [mm]01(01)^n = (01)^{n+1}[/mm].
Du versuchst gerade zu zeigen, dass [mm] $(01)^{n+1}\in [/mm] L(G)$ gilt? Was hat das mit der Induktionsbehauptung zu tun, die wir gerade zeigen wollen?
> > Welche Produktionsregeln könnten Grundlage für den
> Ableitungsschritt sein?
>
> Mögliche Produktionsregeln sind: [mm]S \to 0S1S | 1S0S | \epsilon[/mm]
Ja.
> Ich würd jetzt gerne erst den ersten Teilbeweis, also [mm]L(G) \subseteq L[/mm]
> zeigen, bevor wir mit [mm]L(G) \supseteq L[/mm] weitermachen, ok?
OK.
Starten wir den Induktionsschritt nochmal neu:
> (IS)
> [mm]n\to n+1[/mm]:
>
> Induktionsvoraussetzung: Alle in n Schritten aus S
> ableitbare Wörter über [mm]\{S\}\cup\{0,1\}[/mm] enthalten genauso
> viele 0en wie 1en.
> Induktionsbehauptung: Alle in n+1 Schritten aus S
> ableitbare Wörter über [mm]\{S\}\cup\{0,1\}[/mm] enthalten genauso
> viele 0en wie 1en.
>
> Sei also v ein in n+1 Schritten aus S ableitbares Wort
> über [mm]\{S\}\cup\{0,1\}[/mm] und [mm]S= v_0 \to v_1 \to ...\to v_n \to v_{n+1} = v[/mm]
eine Ableitung von $v$ aus $S$ in $n+1$ Schritten.
Da [mm] $v_n$ [/mm] in $n$ Schritten aus $S$ ableitbar ist, enthält [mm] $v_n$ [/mm] nach Induktionsvoraussetzung genauso viele 1en wie 0en. (*)
> > Welche Produktionsregeln könnten Grundlage für den
> Ableitungsschritt [mm] $v_n\to v_{n+1}$ [/mm] sein?
>
> Mögliche Produktionsregeln sind: [mm]S \to 0S1S | 1S0S | \epsilon[/mm]
Betrachten wir die drei möglichen Fälle separat.
1. Fall: [mm] $v_n\to v_{n+1}$ [/mm] ergibt sich durch eine Anwendung der Regel [mm] $S\to [/mm] 0S1S$.
Dann unterscheiden sich [mm] $v_n$ [/mm] und [mm] $v_{n+1}$ [/mm] genau darin, dass in [mm] $v_{n+1}$ [/mm] gegenüber [mm] $v_n$ [/mm] ein $S$ durch $0S1S$ ersetzt wurde. (**)
Was wollten wir jetzt eigentlich zeigen?
Dass [mm] $v_{n+1}$ [/mm] genauso viele 1en wie 0en hat.
Wie viele 1en hat [mm] $v_{n+1}$? [/mm] Nach (**) genau eine mehr als [mm] $v_n$.
[/mm]
Wie viele 0en hat [mm] $v_{n+1}$? [/mm] Nach (**) genau eine mehr als [mm] $v_n$.
[/mm]
Da [mm] $v_n$ [/mm] gemäß (*) genauso viele 1en wie 0en hat, hat somit auch [mm] $v_{n+1}$ [/mm] genauso viele 1en wie 0en.
Die anderen beiden Fälle überlasse ich dir.
|
|
|
|
