0 Daumen
212 Aufrufe

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

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

\(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}\).

Avatar von 5,6 k

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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community