Pumping Lemma: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Wir stellen uns nun die Frage, ob es auch Sprachen gibt, die nicht durch einen Automaten akzeptiert werden können. Tatsächlich gibt es sehr viele Sprachen, d…“) |
Css (Diskussion | Beiträge) |
||
| Zeile 5: | Zeile 5: | ||
'''Beweis:''' Sei $L$ gegeben und regulär. Ist $L$ endlich, so erfüllt $n = 1 + \max\{|z|\mid z\in L\}$ die Prämisse bereits, da kein solches Wort existiert. Sei also $L$ unendlich und regulär und werde vom deterministischen endlichen Automaten $M$ mit Startzustand $q_0$ und Zustandsmenge $q_1,\ldots,q_{n-1}$ akzeptiert. Sei ein Wort $z\in L$ gegeben, sodass $|z|>n$. Werde nun $z$ akzeptiert durch den Lauf $q_{i_1}\rightarrow \ldots \rightarrow q_{i_{|z|}}$, wobei $q_{i_{|z|}}$ ein Endzustand ist. Da es nur $n$ Zustände gibt, muss in diesem Lauf mindestens ein Zustand doppelt vorkommen, also müssen $k,l$ mit $k<l$ existieren, sodass $q_{i_k} = q_{i_l}$. | '''Beweis:''' Sei $L$ gegeben und regulär. Ist $L$ endlich, so erfüllt $n = 1 + \max\{|z|\mid z\in L\}$ die Prämisse bereits, da kein solches Wort existiert. Sei also $L$ unendlich und regulär und werde vom deterministischen endlichen Automaten $M$ mit Startzustand $q_0$ und Zustandsmenge $q_1,\ldots,q_{n-1}$ akzeptiert. Sei ein Wort $z\in L$ gegeben, sodass $|z|>n$. Werde nun $z$ akzeptiert durch den Lauf $q_{i_1}\rightarrow \ldots \rightarrow q_{i_{|z|}}$, wobei $q_{i_{|z|}}$ ein Endzustand ist. Da es nur $n$ Zustände gibt, muss in diesem Lauf mindestens ein Zustand doppelt vorkommen, also müssen $k,l$ mit $k<l$ existieren, sodass $q_{i_k} = q_{i_l}$. | ||
| − | Das heißt, wir haben einen Lauf der Form $q_{i_1}\rightarrow\ldots\rightarrow q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}\rightarrow\ldots\rightarrow q_{i_{|z|}}$. | + | Das heißt, wir haben einen Lauf der Form $q_{i_1}\rightarrow\ldots\rightarrow \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\rightarrow\ldots\rightarrow q_{i_{|z|}}$. |
Version vom 1. August 2018, 21:29 Uhr
Wir stellen uns nun die Frage, ob es auch Sprachen gibt, die nicht durch einen Automaten akzeptiert werden können. Tatsächlich gibt es sehr viele Sprachen, die nicht von Automaten akzeptiert werden können. Sprachen, die von einem automaten akzeptiert werden, heißen reguläre Sprachen. Das Pumping Lemma gibt ein Kriterium an, das reguläre Sprachen erfüllen müssen.
Lemma: Für jede reguläre Sprache $L$ gibt es eine natürliche Zahl $n$, sodass für alle $z\in L$ mit $|z|>n$ eine Zerlegung $z=uvw$, sodass $|u|+|w|\le n$, $v\neq\varepsilon$ und für alle $i\in\mathbb{N}$ die Wörter $uv^iw\in L$ sind.
Beweis: Sei $L$ gegeben und regulär. Ist $L$ endlich, so erfüllt $n = 1 + \max\{|z|\mid z\in L\}$ die Prämisse bereits, da kein solches Wort existiert. Sei also $L$ unendlich und regulär und werde vom deterministischen endlichen Automaten $M$ mit Startzustand $q_0$ und Zustandsmenge $q_1,\ldots,q_{n-1}$ akzeptiert. Sei ein Wort $z\in L$ gegeben, sodass $|z|>n$. Werde nun $z$ akzeptiert durch den Lauf $q_{i_1}\rightarrow \ldots \rightarrow q_{i_{|z|}}$, wobei $q_{i_{|z|}}$ ein Endzustand ist. Da es nur $n$ Zustände gibt, muss in diesem Lauf mindestens ein Zustand doppelt vorkommen, also müssen $k,l$ mit $k<l$ existieren, sodass $q_{i_k} = q_{i_l}$.
Das heißt, wir haben einen Lauf der Form $q_{i_1}\rightarrow\ldots\rightarrow \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\rightarrow\ldots\rightarrow q_{i_{|z|}}$.
