0 Daumen
1,5k Aufrufe

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! :)

Avatar von

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

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

Wie sieht denn dein gewähltes Wort aus?

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
...

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

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

Ich habe dir Mal eine Antwort geschrieben.

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

1 Antwort

0 Daumen
 
Beste Antwort

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.

Avatar von

Vielen Dank!

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

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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community