Logik/reguläre Sprachen: Pumping Lemma

04.06.2012, 18:23

bandchef

Logik/reguläre Sprachen: Pumping Lemma

Aufgabe:
Beweisen oder widerlegen sie mit dem Pumping-Lemma, dass die folgende Sprache regulär ist:

$\begin{eqnarray*} L=\{ 0^p | \text{p ist keine Primzahl} \} \end{eqnarray*}$

Hi Leute!

Ich hab mit dem Pumping-Lemma so meine Probleme. Ich hoffe ihr könnt mir an dieser Stelle weiterhelfen! Ich hab dann mal so angefangen:

Wir treffen am Anfang eine Annahme: L ist regulär.

Sei $\begin{eqnarray*} n_0 \end{eqnarray*}$ die Konstante des PL, dann gilt: $\begin{eqnarray*} n_0 \geq 1 \end{eqnarray*}$ mit $\begin{eqnarray*} n_0 \in \mathbb N \end{eqnarray*}$ .

$\begin{eqnarray*} z = 0^{n_0} \end{eqnarray*}$ mit $\begin{eqnarray*} z = uvw \end{eqnarray*}$ , $\begin{eqnarray*} |uv| \leq n_0 \end{eqnarray*}$ , $\begin{eqnarray*} |v| \geq 1 \end{eqnarray*}$ und $\begin{eqnarray*} |z| \geq n_0 \end{eqnarray*}$

Ab dieser Stelle hab ich nun meine Probleme. Jetzt muss ich eine Zerlegung in uvw angeben. Aber genau das verstehe ich immer nicht. Könnt ihr mir ab hier weiterhelfen?

04.06.2012, 18:37

kiste

Auf diesen Beitrag antworten »

RE: Logik/reguläre Sprachen: Pumping Lemma

Zitat:

Original von bandchef
Ab dieser Stelle hab ich nun meine Probleme. Jetzt muss ich eine Zerlegung in uvw angeben. Aber genau das verstehe ich immer nicht. Könnt ihr mir ab hier weiterhelfen?

Nein du musst zeigen: Für jede Zerlegung gibt es ein i so dass uv^iw die Länge einer Primzahl hat.

Die Sprache ist sicherlich nicht regulär, ad hoc sehe ich aber die Konstruktion nicht mit der wir die Primzahl bekommen. Ein guter Start ist es vllt. das Wort z obda mit ungerader Länge zu nehmen.

Einfacher ist es jedoch das Komplement von L zu betrachten und darauf das PL anzuwenden.

04.06.2012, 18:44

bandchef

Auf diesen Beitrag antworten »

Hm, vielleicht es dann einfacher, wenn ich andere Sprache als Beispiel angebe:

$\begin{eqnarray*} L = \{ 0^{k^2} | k \in \mathbb N \} \end{eqnarray*}$

Wir treffen am Anfang eine Annahme: L ist regulär.

Sei $\begin{eqnarray*} n_0 \end{eqnarray*}$ die Konstante des PL, dann gilt: $\begin{eqnarray*} n_0 \geq 1 \end{eqnarray*}$ mit $\begin{eqnarray*} n_0 \in \mathbb N \end{eqnarray*}$ .

$\begin{eqnarray*} z = 0^{{n_0}^2} \end{eqnarray*}$ , $\begin{eqnarray*} z \in L \end{eqnarray*}$ , $\begin{eqnarray*} |z| \geq n_0 \end{eqnarray*}$

Jede gültige Zerlegung hat die Form:

Hier hab ich nun wieder meine Probleme...

Edit: Einfacher ist es jedoch das Komplement von L zu betrachten und darauf das PL anzuwenden. Diesen Satz verstehe ich nicht ganz. Das Komplement von L enthält ja alle Wörter der Sprache L die nicht in L enthalten sind, oder? Ich hab immer gedacht, dass die "Annahme" am Anfang des Beweises widerlegt werden muss. Da ich eben annehme, dass die Sprache regulär ist, reicht es zu zeigen, dass sie es eben nicht ist.

Dass ich eine Zerlegung für uv^iw finden muss ist klar; dass war grad nur ein Tipfehler... Dennoch hab ich das Problem, dass ich eine Zerlegung angeben muss, die für ein $\begin{eqnarray*} i \in \mathbb N \end{eqnarray*}$ zeigt, dass die Sprache nicht regulär ist.

04.06.2012, 19:34

kiste

Auf diesen Beitrag antworten »

Bei deinem Quadratbeispiel hilft doch schon i=2.

Das mit dem Komplement gilt weil $\begin{eqnarray*} L \in REG \Leftrightarrow \overline L \in REG \end{eqnarray*}$ . Deswegen kann man auch zeigen dass das Komplement von L nicht regulär ist.

05.06.2012, 17:35

bandchef

Auf diesen Beitrag antworten »

Ich hab jetzt das hier auf meinem Blatt stehen:

$\begin{eqnarray*} L = \{ 0^{k^2} |k \in \mathbb N \} \end{eqnarray*}$

Annahme: L ist regulär.

Sei $\begin{eqnarray*} n_0 \end{eqnarray*}$ die Konstante des Pl, dann gilt: $\begin{eqnarray*} n_0 \geq 1, n_0 \in \mathbb N \end{eqnarray*}$ .

$\begin{eqnarray*} z = 0^{{n_0}^2} \end{eqnarray*}$ mit $\begin{eqnarray*} |z| \geq n_0, z \in \mathbb N \end{eqnarray*}$

Sei z = uvw eine Zerlegung von z mit $\begin{eqnarray*} |uv| \leq n_0, |v| \geq 1 \end{eqnarray*}$ .

$\begin{eqnarray*} z = ... \end{eqnarray*}$

Wie sieht diese Zerlegung nun aus? Das ist immer das Problem, dass ich beim PL hab...

05.06.2012, 19:24

kiste

Auf diesen Beitrag antworten »

Zitat:

Original von bandchef
Wie sieht diese Zerlegung nun aus? Das ist immer das Problem, dass ich beim PL hab...

Weiß man nicht, musst halt einen Widerspruch finden egal wie die Zerlegung aussieht.

Neue Frage »

Antworten »

Logik/reguläre Sprachen: Pumping Lemma

Verwandte Themen