Pumping Lemma für Wortlänge ist eine Zweierpotenz

Question 1

Frage: Wie zeigt man mit Pumping Lemma, dass folgende Sprache über dem Alphabet $$\Sigma= \{0,1,2\}$$ nicht von einem DFA akzeptiert wird:
$${L= \{ w\in\Sigma^*\mid \lvert w \rvert \text{ ist Zweierpotenz}\} }$$

Wie Pumping Lemma grundsätzlich funktioniert, doch wie genau macht man das in diesem Fall?

Vielen Dank für eine Antwort! :)

Question 2

Nehme an, dass L regulär sei. Nun führe fort.

Question 3

Mein Problem liegt darin, dass ich nicht weiß, in welche 3 Teile ich das Wort teilen kann.

Question 4

Wie sieht denn dein gewähltes Wort aus?

Question 5

Ich weiß leider auch nicht, welches Wort ich hier wählen kann bzw wie ich das allgemein aufschreiben kann.

Wörter der Sprache sind ja z.B.:
1
02
2100
10201220
...

Question 6

Wie bewirke ich, dass die Wortlänge eine Zweierpotenz ist?

Question 7

$2^n=\underbrace{2\cdot \ldots \cdot 2}_{n \text{ Mal}}$

Question 8

Ich habe dir Mal eine Antwort geschrieben.

Question 9

ok, Danke. Mein Problem liegt darin, dass ich nicht weiß, wie ich ein solches Wort allgemein aufschreiben kann...

Question 10

Angenommen, $L\in \operatorname{REG}$.

Dann gibt es eine Pumpinglänge $n>0$ und wir können $w=0^{2^n}$ wählen, denn $\lvert w \rvert > n$ und $w\in L$.
Seien $u,v,w\in \Sigma^*$ beliebig und gelte $|uv|\leq n$ und $|v|>0$. Dann müssen in $u$ und $v$ nur $0$en enthalten sein, egal wie man das Wort zerteilt.

Sei $u:=0^k$, $v:=0^l$ mit $k,\,l\in \mathbb{N}$, $k+l\leq n$, $l>0$ und $w:=0^{2^n-l-k}$. Betrachten wir jetzt zum Beispiel $i=0$, haben wir: $$\begin{aligned}uv^0w &= 0^k.0^{2^n-l-k}\\&=0^{2^n-l}\notin L,\end{aligned}$$ weil $l>0$ und $l<n$. Widerspruch, $L$ war nicht regulär.

Question 11

Vielen Dank!

Ich hatte nicht daran gedacht, dass man ja auch einfach nur ein Zeichen aus dem Alphabet wählen kann...

Question 12

Ja, gerne. Als du die Frage als Kommentar geschrieben hattest, hatte ich gerade die Antwort gepostet. Sonst hätte ich dir das natürlich nicht vorweggenommen und nur auf dein Kommentar geantwortet. Aber da war es dann schon zu spät. :D

Doesbaddel · Answer 1 · 2020-11-28T11:35:29+0000

Angenommen, $L\in \operatorname{REG}$.

Dann gibt es eine Pumpinglänge $n>0$ und wir können $w=0^{2^n}$ wählen, denn $\lvert w \rvert > n$ und $w\in L$.
Seien $u,v,w\in \Sigma^*$ beliebig und gelte $|uv|\leq n$ und $|v|>0$. Dann müssen in $u$ und $v$ nur $0$en enthalten sein, egal wie man das Wort zerteilt.

Sei $u:=0^k$, $v:=0^l$ mit $k,\,l\in \mathbb{N}$, $k+l\leq n$, $l>0$ und $w:=0^{2^n-l-k}$. Betrachten wir jetzt zum Beispiel $i=0$, haben wir: $$\begin{aligned}uv^0w &= 0^k.0^{2^n-l-k}\\&=0^{2^n-l}\notin L,\end{aligned}$$ weil $l>0$ und $l<n$. Widerspruch, $L$ war nicht regulär.

Vielen Dank!
Ich hatte nicht daran gedacht, dass man ja auch einfach nur ein Zeichen aus dem Alphabet wählen kann... — Gast, 28 Nov 2020
Ja, gerne. Als du die Frage als Kommentar geschrieben hattest, hatte ich gerade die Antwort gepostet. Sonst hätte ich dir das natürlich nicht vorweggenommen und nur auf dein Kommentar geantwortet. Aber da war es dann schon zu spät. :D — Doesbaddel, 28 Nov 2020

Pumping Lemma für Wortlänge ist eine Zweierpotenz

1 Antwort

Ähnliche Fragen

Eingabetools:

Beliebte Fragen:

Heiße Lounge-Fragen: