0 Daumen
232 Aufrufe

Frage:

Pumping Lemma


blob.png

Text erkannt:

Zeigen Sie mithilfe des Pumping-Lemmas, dass die Sprache \( L=\left\{w \in \Sigma^{*}:|w|\right. \) ist eine Primzahl \( \} \) über dem Alphabet \( \Sigma=\{0,1, \ldots, 9\} \) von keinem DFA entschieden werden kann.


Code:

Avatar von

1 Antwort

0 Daumen

Sei \(p\in \mathbb{N}\).

Sei \(xyz\in L\) mit \(|xy| \leq p\) und \(|y|\geq 1\).

Dann ist \(xy^{|xz|}z\notin L\).

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community