0 Daumen
53 Aufrufe

Zeigen Sie, dass \(L_{1}:=L\left((a \cup b)^{*} \cdot(a a \cup b b) \cdot(a \cup b)^{*}\right) \cup\left\{w \in\{a, b\}^{*}\mid \lvert w \rvert \text { ist Primzahl }\right\}\) die Pumping-Eigenschaft besitzt, aber nicht regulär ist.


Ansatz:

Erstmal zur PE:

Umgeschrieben kann man die Sprache wie folgt definieren:  \(L_{1}:=\{w \in\{a, b\}^{*}\mid aa \text{ ist Teilwort } \lor bb \text{ ist Teilwort } \lor \lvert w \rvert \text { ist Primzahl }\}\)

Ich wähle  n=3 die Pumping-Länge. Nun betrachte ich die Fälle

Fall 1: aa ist TW von w

1a) w beginnt mit aa, also kann ich w wie folgt aufteilen:

$$x=aa \quad y=w_3 \quad z= w_4 \dots w_{\lvert w\rvert}$$.

Also haben Aufteilung gefunden, ist ok.

1b) w beginnt nicht mit aa

$$x=\lambda \quad y=w_1 \quad z= w_2 \dots w_{\lvert w\rvert}$$. Wobei in \(z\) das \(aa\) enthalten ist.


Fall 2 bb ist TW  analog zu Fall 1

Fall 3 \(\neg(\text{ Fall1 } \land \text{ Fall2 })\), also w enthält nicht aa und nicht bb, d.h. nach jedem a muss ein b folgen und nach jedem b ein a und Länge von w ist Primzahl

3a) w beginnt mit a

Nun habe ich Probleme, weiter zu machen: Ich habe keine Ahnung, wie ich hier xyz wählen soll, damit die Länge eine Primzahl bleibt. Meiner Meinung nach kann man selbst mit den Vereinigungen die PE nicht zeigen, aber laut Aufgabenstellung soll die Sprache ja die PE besitzen. Hilfe wäre sehr nett!

3b) w beginnt nicht mit a

Gleiches Problem wie bei 3a)

von
¬( Fall1 ∧ Fall2 ), also w enthält nicht aa und nicht bb

"w enthält nicht aa und nicht bb" ist ¬Fall1 ∧ ¬Fall2. Das Distributivgesetz

        ¬Fall1 ∧ ¬Fall2 ≡ ¬(Fall1 ∧ Fall2)

gibt es nicht. Verwende stattdessen eines der De Morgansche Gesetze, nämlich

        ¬Fall1 ∧ ¬Fall2 ≡ ¬(Fall1 ∨ Fall2).

Danke hab's hinbekommen.

1 Antwort

0 Daumen
damit die Länge eine Primzahl bleibt.

Das braucht sie nicht. Es reicht wenn du so pumpst, dass die resultierenden Wörter aus einem anderen Grund in L1 sind.

nach jedem a muss ein b folgen und nach jedem b ein a

Das hilft beim Pumpen enorm.

Gleiches Problem wie bei 3a)

Gleiche Lösung wie bei 3a)

von 1,7 k  –  ❤ Bedanken per Paypal

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...