Sind die folgenden Sprachen regulär?

Question

Frage:

Hey ich bereite mich gerade auf eine Klausur vor und bin dabei auf die folgenden Aufgaben gestoßen bei denen ich leider nicht weiß wie ich sie lösen soll.

Aufgabe 3

a) Ist die folgende Sprache regulär?

        \(L_{k}=\left\{w=a_{1} a_{2} \ldots a_{n} \in\{0,1\}^{*} \mid n \geq k \text { und } a_{k}=1\right\}\)

Beweisen Sie Ihre Antwort! Wenn die Sprache regulär ist, beweisen Sie dies durch die Angabe eines vollständig beschriebenen Automaten (keine Grammatik, kein regulärer Ausdruck, keine Äquivalenzklassenaufteilung - es muss ein Automat sein). Argumentieren Sie dann, warum Ihr Automat alle Wörter der Sprache erkennt und kein Wort, das nicht in der Sprache ist (Beweis der Teilmengeninklusion in beide Richtungen). Wenn die Sprache nicht regulär ist, beweisen Sie dies mit Hilfe des Puming Lemmas oder mit dem Satz von Myhill-Nerode.

2. Sei L eine reguläre Sprache. Beweisen Sie:

a) Die Präfixmenge P(L) = {w ∈ ∑* | ∃ x ∈ ∑* mit wx ∈ L} ist ebenfalls regulär

b) Die Suffixmenge S(L) = {w ∈ ∑* | ∃ x ∈ ∑* mit xw ∈ L} ist ebenfalls regulär

Vielen Dank im Voraus für die Hilfe

Answer 1

\(L_{k}=\left\{w=a_{1} a_{2} \ldots a_{n} \in\{0,1\}^{*} \mid n \geq k \text { und } a_{k}=1\right\}\)

Die Sprache ist regulär. Ein Automat liest die ersten \(k-1\) Zeichen und prüft dann, ob das nächste Zeichen eine \(1\) ist.

P(L) = {w ∈ ∑* | ∃ x ∈ ∑* mit wx ∈ L}

Gegeben ist ein Automat, der \(L\) erkennt. Baue daraus einen Automaten, der \(P(L)\) erkennt.

S(L) = {w ∈ ∑* | ∃ x ∈ ∑* mit xw ∈ L}

Sei \(M^\mathrm{R}\) die Sprache, die man bekommt indem man die Reihenfolge der Buchstaben von Wörtern der Sprache \(M\) umkehrt.

Dann ist \(S(L) = (P(L^\mathrm{R}))^\mathrm{R}\).

Comments

Wie würde man denn aus dem Automaten für L den Automaten für P(L) konstruieren?