Revision history for FormaleSprachen
Deletions:
L ist eine reguläre Sprache über X.
Es gibt ein n ∈ N entsprechend PL
so, dass für alle x ∈ L mit |x|≥ n gilt:
Es gibt Teilwörter u, v, w ∈ X* mit
~-x =uvw,
~-|uv| ≤ n (bzw. |vw| ≤ n),
~-|v| ≥ 1 und
~-""uv<sup>i</sup>w ∈ L"" ∀ i ∈ N""<sub>0</sub>"".
Additions:
PumpingLemma
Deletions:
[[http://de.wikipedia.org/wiki/Pumping-Lemma Pumping-Lemma]] (PL) liefert eine notwendige Bedingung für reguläre Sprachen.
Die Umkehrung des PL liefert die Möglichkeit, Sprachen auf Regularität zu überprüfen.
Genauer gesagt liefert das PL die Möglichkeit den Beweis zu erbringen, dass eine formale Sprache __nicht regulär__ ist.
Allerdings kann der Beweis, dass eine formale Sprache regulär ist mit dem PL nicht erbracht werden.
===Beispiel 1===
Eine Sprache L ist definiert durch
%%L = {x ∈ {a, b}* | x = a""<sup>k</sup>b<sup>k</sup>"", k ∈ N}%%
{{image url="images/AtfsFormaleSprachenBsp1.png"}}
===Beispiel 2===
L = {a""<sup>n</sup> b<sup>2n</sup>"", | n ∈ N}
1. wähle n entsprechend PL
2. wähle Exemplaar x ∈ L: a""<sup>n</sup> b<sup>2n</sup>""
3. Betrachte Zerlegungen in Teilweörter
4. Feststellung für alle diese Zerlegungen v in a""<sup>n</sup>""
5. ⇒ ""uv<sup>i</sup>w"" nur a's vervielfältigt
⇒ 2""|uv<sup>i</sup>w|<sub>a</sub> ≠ |uv<sup>i</sup>w|<sub>a</sub>""
Additions:
%%L = {x ∈ {a, b}* | x = a""<sup>k</sup>b<sup>k</sup>"", k ∈ N}%%
Deletions:
Additions:
{{image url="images/AtfsFormaleSprachenBsp1.png"}}
No Differences
Additions:
Formale Sprachen - die Sprache endlicher Zustandsautomaten (SkriptAtfsEckNr1, S. 25)
Deletions:
Additions:
Genauer gesagt liefert das PL die Möglichkeit den Beweis zu erbringen, dass eine formale Sprache __nicht regulär__ ist.
Allerdings kann der Beweis, dass eine formale Sprache regulär ist mit dem PL nicht erbracht werden.
Allerdings kann der Beweis, dass eine formale Sprache regulär ist mit dem PL nicht erbracht werden.
Additions:
5. ⇒ ""uv<sup>i</sup>w"" nur a's vervielfältigt
Deletions:
Additions:
===Beispiel 1===
===Beispiel 2===
L = {a""<sup>n</sup> b<sup>2n</sup>"", | n ∈ N}
1. wähle n entsprechend PL
2. wähle Exemplaar x ∈ L: a""<sup>n</sup> b<sup>2n</sup>""
3. Betrachte Zerlegungen in Teilweörter
4. Feststellung für alle diese Zerlegungen v in a""<sup>n</sup>""
5. ⇒ ""uv<sup>i</sup>w nur a's vervielfältigt
⇒ 2""|uv<sup>i</sup>w|<sub>a</sub> ≠ |uv<sup>i</sup>w|<sub>a</sub>""
===Beispiel 2===
L = {a""<sup>n</sup> b<sup>2n</sup>"", | n ∈ N}
1. wähle n entsprechend PL
2. wähle Exemplaar x ∈ L: a""<sup>n</sup> b<sup>2n</sup>""
3. Betrachte Zerlegungen in Teilweörter
4. Feststellung für alle diese Zerlegungen v in a""<sup>n</sup>""
5. ⇒ ""uv<sup>i</sup>w nur a's vervielfältigt
⇒ 2""|uv<sup>i</sup>w|<sub>a</sub> ≠ |uv<sup>i</sup>w|<sub>a</sub>""
Deletions:
Additions:
Formale Sprachen - die Sprache endlicher Zustandsautomaten
Deletions:
Additions:
L = {x ∈ {a, b}* | x = a""<sup>k</sup>b<sup>k</sup>"", k ∈ N}
Deletions:
Additions:
===Beispiel===
Eine Sprache L ist definiert durch
L = {x ∈ {a, b}*, | x = a""<sup>k</sup>b<sup>k</sup>"", k ∈ N}
Eine Sprache L ist definiert durch
L = {x ∈ {a, b}*, | x = a""<sup>k</sup>b<sup>k</sup>"", k ∈ N}
Additions:
~-""uv<sup>i</sup>w ∈ L"" ∀ i ∈ N""<sub>0</sub>"".
Deletions:
Additions:
Es gibt ein n ∈ N entsprechend PL
Es gibt Teilwörter u, v, w ∈ X* mit
~-x =uvw,
~-|uv| ≤ n (bzw. |vw| ≤ n),
~-|v| ≥ 1 und
~-""uv<sup>2</sup>w ∈ L"" ∀ i ∈ N""<sub>0</sub>"".
Es gibt Teilwörter u, v, w ∈ X* mit
~-x =uvw,
~-|uv| ≤ n (bzw. |vw| ≤ n),
~-|v| ≥ 1 und
~-""uv<sup>2</sup>w ∈ L"" ∀ i ∈ N""<sub>0</sub>"".
Deletions:
Es gibt Teilwörter u, v, w ∈ X* mit x =uvw,
|uv| ≤ n (bzw. |vw| ≤ n),
|v| ≥ 1 und
""uv<sup>2</sup>w ∈ L"" ∀ i ∈ N""<sub>0</sub>"".
Additions:
==a==Pumping-Lemma==a==
==a==Struktureigenschaften regulärer Sprachen==a==
L ist eine reguläre Sprache über X.
Es gibt ein n ∈ N entsprechend PL ->,
so, dass für alle x ∈ L mit |x|≥ n gilt:
Es gibt Teilwörter u, v, w ∈ X* mit x =uvw,
|uv| ≤ n (bzw. |vw| ≤ n),
|v| ≥ 1 und
""uv<sup>2</sup>w ∈ L"" ∀ i ∈ N""<sub>0</sub>"".
==a==Struktureigenschaften regulärer Sprachen==a==
L ist eine reguläre Sprache über X.
Es gibt ein n ∈ N entsprechend PL ->,
so, dass für alle x ∈ L mit |x|≥ n gilt:
Es gibt Teilwörter u, v, w ∈ X* mit x =uvw,
|uv| ≤ n (bzw. |vw| ≤ n),
|v| ≥ 1 und
""uv<sup>2</sup>w ∈ L"" ∀ i ∈ N""<sub>0</sub>"".
Additions:
Die Sprache endlicher Zustandsautomaten
[[http://de.wikipedia.org/wiki/Pumping-Lemma Pumping-Lemma]] (PL) liefert eine notwendige Bedingung für reguläre Sprachen.
Die Umkehrung des PL liefert die Möglichkeit, Sprachen auf Regularität zu überprüfen.
[[http://de.wikipedia.org/wiki/Pumping-Lemma Pumping-Lemma]] (PL) liefert eine notwendige Bedingung für reguläre Sprachen.
Die Umkehrung des PL liefert die Möglichkeit, Sprachen auf Regularität zu überprüfen.
Additions:
=====Formale Sprachen=====
