Pumping Lemma - Versionsgeschichte

Css: /* Beispiele */

2018-08-01T20:03:44Z

‎Beispiele

Css am 1. August 2018 um 19:58 Uhr

2018-08-01T19:58:31Z

Css am 1. August 2018 um 19:35 Uhr

2018-08-01T19:35:55Z

Css am 1. August 2018 um 19:29 Uhr

2018-08-01T19:29:50Z

Css: 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…“

2018-08-01T19:28:12Z

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…“

Neue Seite

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 q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}\rightarrow\ldots\rightarrow q_{i_{|z|}}$.

@@ Zeile 15: / Zeile 15: @@
 ** Ist $k$ eine korrekte Klammerung, so auch $(k)$
 ** Sind $k$ und $l$ korrekte Klammerungen, so auch $kl$
-Jedes Wort enthält die Teilzeichenkette $()$, die beliebig oft wiederholbar ist. Also erfüllt diese Sprache das Pumping-Lemma. Sie ist aber trotzdem nicht regulär.
+Jedes Wort enthält die Teilzeichenkette $()$, die beliebig oft wiederholbar ist. Also erfüllt diese Sprache das Pumping-Lemma. Sie ist aber trotzdem nicht regulär: Angenommen ein Automat $M$ mit $n$ Zuständen akzeptiere genau diese Sprache. Dann muss $M$ auch $(^{n+1})^{n+1}$ akzeptieren. Dann muss es, analog zum Beweis des Pumpinglemma, einen Lauf geben, der $(^{n+1}$ matcht (aber nicht in einem Endzustand endet), und dieser muss mindestens eine Wiederholung enthalten. Diese Wiederholung matcht dann auf einen Ausdruck $(^k$, und das bedeutet, dass dann auch das Wort $(^{n+1+k})^{n+1}$ gematcht wird, welches kein korrekt geklammerter Ausdruck mehr ist. Die Sprache kann also nicht regulär sein.

← Nächstältere Version		Version vom 1. August 2018, 19:58 Uhr
Zeile 6:		Zeile 6:

	Das heißt, wir haben einen Lauf der Form $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\underbrace{\rightarrow\ldots\rightarrow q_{i_{\|z\|}}}_w$. Dann ist aber auch der Lauf $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u q_{i_k} \underbrace{\rightarrow\ldots\rightarrow q_{i_{\|z\|}}}_w$ korrekt, und Läufe der Form $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v \ldots \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\underbrace{\rightarrow\ldots\rightarrow q_{i_{\|z\|}}}_w$. QED.		Das heißt, wir haben einen Lauf der Form $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\underbrace{\rightarrow\ldots\rightarrow q_{i_{\|z\|}}}_w$. Dann ist aber auch der Lauf $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u q_{i_k} \underbrace{\rightarrow\ldots\rightarrow q_{i_{\|z\|}}}_w$ korrekt, und Läufe der Form $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v \ldots \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\underbrace{\rightarrow\ldots\rightarrow q_{i_{\|z\|}}}_w$. QED.
		+
		+	== Beispiele ==
		+
		+	* Die Sprache $\{a^kb^k\mid k\in\mathbb{N}\}$ ist nicht regulär, wie man leicht mit dem Pumpinglemma sieht.
		+	* Die Sprache $\{a^p\mid p \mbox{ Prim}\}$ ist nicht regulär, denn sonst müsste es zu jeder Primzahl $p$ zahlen $q,r<p$ geben, sodass alle $q+nr$ ebenfalls prim sind.
		+	* Das Pumpinglemma ist eine notwendige, aber keine hinreichende Bedingung, damit eine Sprache regulär ist. Die Sprache der korrekten Klammerungen sei rekursiv definiert durch
		+	** $()$ ist eine korrekte Klammerung
		+	** Ist $k$ eine korrekte Klammerung, so auch $(k)$
		+	** Sind $k$ und $l$ korrekte Klammerungen, so auch $kl$
		+	Jedes Wort enthält die Teilzeichenkette $()$, die beliebig oft wiederholbar ist. Also erfüllt diese Sprache das Pumping-Lemma. Sie ist aber trotzdem nicht regulär.

← Nächstältere Version		Version vom 1. August 2018, 19:35 Uhr
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 \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\rightarrow\ldots\rightarrow q_{i_{\|z\|}}$.	+	Das heißt, wir haben einen Lauf der Form $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\underbrace{\rightarrow\ldots\rightarrow q_{i_{\|z\|}}}_w$. Dann ist aber auch der Lauf $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u q_{i_k} \underbrace{\rightarrow\ldots\rightarrow q_{i_{\|z\|}}}_w$ korrekt, und Läufe der Form $\underbrace{q_{i_1}\rightarrow\ldots\rightarrow}_u \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v \ldots \underbrace{q_{i_k}\rightarrow\ldots\rightarrow q_{i_k}}_v\underbrace{\rightarrow\ldots\rightarrow q_{i_{\|z\|}}}_w$. QED.

← Nächstältere Version		Version vom 1. August 2018, 19:29 Uhr
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\|}}$.