Kontextfreie Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:40 Sa 08.01.2011 | | Autor: | Loko |
| Aufgabe | Die kontextfreie Grammatik [mm] G_{2a} [/mm] = ({A,S},{a,b},P,S) mit den Regeln:
S::= Aa|Sb
A::= Sa|Ab|a
erzeugt Wörter der Sprache [mm] L_{2a} [/mm] = {w [mm] \in [/mm] {a,b} ^{+}| anzahl(a,w)mod 2 = 0}.
Für jede Ableitung S [mm] \overrightarrow{P} [/mm] w (mit * drüber) gilt zudem w = Xu mit u [mm] \in [/mm] {a,b} ^{*} und X [mm] \in [/mm] { [mm] \lambda,S,A [/mm] }. Beweise durch vollständige Induktion über die Länge der Ableitung, dass [mm] \forall [/mm] u [mm] \in [/mm] {a,b} ^{*}, X [mm] \in [/mm] { [mm] \lambda,S,A [/mm] } folgende Behauptung gilt:
S [mm] \overrightarrow{P} [/mm] Xu (mit *) [mm] \Rightarrow [/mm] anzahl(a,u) mod 2 = [mm] \begin{cases} 0, & \mbox{falls } X \in { \lambda,S } \\ 1, & \mbox{falls } X=A. \end{cases} [/mm] |
Ich habe jetzt den Induktionsanfang versucht, hier also meine erste Frage ob das soweit richtig ist:
wg. S::= Aa|Sb ist X = S oder A (nicht [mm] \lambda).
[/mm]
(i) X = S: S [mm] \to [/mm] Su [mm] \Rightarrow [/mm] anzahl(a,u) mod 2 = 0, da X [mm] \in [/mm] { [mm] \lambda,S [/mm] }.
Stimmt, da u = b wg S::= Sb
(ii) X = S: S [mm] \to [/mm] Au [mm] \Rightarrow [/mm] anzahl(a,u) mod 2 = 1, da X=A.
Stimmt, da u=a wg S::= Aa.
Beim Induktionsschritt weiß ich aber gerade nicht weiter, da ich schon nicht genau weiß wie der zweite Ableitungsschritt aussieht.
Ist das dann z.B.: Sb [mm] \to [/mm] Xu, wobei dann X wieder wie bei S [mm] \to [/mm] Xu entweder S oder A ist?
Lg Loko
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:21 Mo 10.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
