Zeigen Sie mithilfe des Pumping-Lemmas,

Question

Frage:

Pumping Lemma

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:

Answer 1

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

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

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