0 Daumen
500 Aufrufe

Frage:

Ich soll zeigen das die Sprache regulär oder nicht regulär ist. Bin mir ziemlich sicher das man das in beiden fällen hier mit dem Pumping Lemma machen muss, da ich ebenfalls der Meinung bin, beide Sprachen sind nicht regulär. Das Alphabet ist (a,b,c)

$$\text { a) } L_{3}=\left\{w \in \Sigma^{*} \mid \#_{a}(w) \text { ist eine Zweierpotenz }\right\}$$

$$\text { b) } L_{1}=\left\{w \in \Sigma^{*} \mid \#_{a}(w) \text { ist eine Primzahl }\right\}$$

das #a(w) ist die Anzahl der a im Wort. Beim ersten muss das Wort also 1,2,4,8 .... a haben und beim zweiten eben eine Primzahl. Mir ist nicht ganz klar wie ich hier das Pumping Lemma anwenden muss, allerdings habe ich es bisher auch nur bei sehr einfachen Beispielen gemacht. Die Aufgabe mit den Primzahlen soll anscheinend ziemlich schwer sein.

Ich hoffe mir kann hier jemand helfen!

Avatar von

Nimm an, dass L regulär ist. Dann müsste es laut Definition eine Pumpinglänge n > 0 geben und man kann ein Wort aus der Sprache L mit |w| > n wählen, welches sich für den Beweis eignet. Hier könntest du zum Beispiel \(w = a^{2^n}\) wählen.

Nehme an, dass \(u,v,w \in \Sigma^*\) beliebig sind und das \(|uv|\leq n\) und \(|v|>0\) gilt. Nun zeigst du, dass für ein bestimmtes i, \(uv^iw\notin L\) ist. Dann kannst du schlussfolgern, dass L nicht regulär war.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community