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)
