Benutzer-Werkzeuge
se:automatentheorie
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung | Nächste Überarbeitung Beide Seiten der Revision | ||
|
se:automatentheorie [2008-12-01 15:10] stefan |
se:automatentheorie [2008-12-01 15:17] stefan |
||
|---|---|---|---|
| Zeile 59: | Zeile 59: | ||
| * Bedingung: |uv| ≤ n, |v| ≥ 1, n muss mindestens die Anzahl der Zustände sein | * Bedingung: |uv| ≤ n, |v| ≥ 1, n muss mindestens die Anzahl der Zustände sein | ||
| * => uv<sup>i</sup>w ∈ L ∀ i ∈ N (v<sup>i</sup>: v wird i-mal vervielfältigt) | * => uv<sup>i</sup>w ∈ L ∀ i ∈ N (v<sup>i</sup>: v wird i-mal vervielfältigt) | ||
| + | |||
| + | ==== Beispiel ==== | ||
| + | Nachweis, dass folgende Sprache nicht regulär ist, durch Umkehrung des Pumping-Lemma: | ||
| + | |||
| + | L = { x ∈ {a, b} | x = a<sup>n</sup>b<sup>n</sup> für n ∈ N} | ||
| + | |||
| + | - wähle n entsprechend des Pumping-Lemmas | ||
| + | - wähle Exemplar/Wort x ∈ L: a<sup>n</sup>b<sup>n</sup> | ||
| + | - betrachte Zerlegungen in Teilwörter x = uvw mit |uv| ≤ n, |v| ≥ 1 | ||
| + | - für alle Zerlegungen von x in Teilwörter mit x = uvw und v in a<sup>n</sup> werden nur a's vervielfältigt => |uv<sup>i</sup>w|<sub>a</sub> ≠ |uv<sup>i</sup>w|<sub>b</sub> | ||
| ===== ToDo ===== | ===== ToDo ===== | ||
| * Skript Herold lesen | * Skript Herold lesen | ||
se/automatentheorie.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
