3. Reguläre Sprache beweisen

Reguläre Sprache beweisen

  • V

    Aufgabe:

    Sei L∈ΣBool⋆L \in \Sigma_{\text{Bool}}^{\star} eine reguläre Sprache. Beweisen oder widerlegen Sie die folgende Aussage Even(L)={w∈L∣∣w∣mod2=0}Even(L) = \{w \in L | |w| mod 2 = 0 \} IST regulär.

    Hinweis: Es ist ausreichend, wenn Sie ein Gegenbeispiel zeigen oder eine Konstruktionsvorschrift angeben, welche beschreibt, wie man aus einem Automaten für L einen Automaten gewinnen kann, der Even(L) erkennt.

    Ich hab nun zu dieser Aufgabe ein paar Fragen. Mir ist klar, dass die Sprache L eine reguläre Sprache ist. Das ist ja angegeben mit dem ersten Satz aus der Aufgabe. Mir ist aber nicht klar, was die Funktion Even() mit der Sprache macht.

    Wenn ich Even ins Deutsche übersetze, dann heißt das so viel wie "ebnen", "ausgleichen", "glätten", u.ä. Was aber hat das hier nun für eine Bedeutung?

    0
  • M

    Hatten wir nicht genau die Sprache erst letztens? "Even" heißt gerade (Zahl), im Gegensatz zu "odd" = ungerade.

    PS: Es gilt natürlich derselbe Ratschlag wie jedes Mal: Lern endlich, Definitionen zu verstehen.

    0
  • K

    Even(L) ist eine Menge parameterisiert durch L. Genau wie f(x) = x^2 eine Funktion ist mit Parameter x. f(x) konstruiert bei konkretem x eine neue Zahl y = f(x). Even(L) konstruiert aus einem konkretem L eine neue Sprache L'. Die Angabe von Parametern kann auf unterschiedliche Art und Weise geschrieben werden. D.h. es geht auch anders. In dem Fall von Even(L) = {w in L | |w|%2=0} werden alle geraden Woerter aus L herausgefilter und bilden die neu konstruierte Sprache. Zur Erinerung: Eine Sprache ist eine Menge aus Woertern. Also alle Woerter der neuen Sprache sind auch in L enthalten. Jedoch enthaelt L' nur die Woerter aus L mit gerader Laenge. Das ist vergleichbar Mit der Menge der natuerlichen Zahlen. Alle gerden Zahlen sind auch in N, aber nicht alle Zahlen aus N sind gerade.

    Dass Even(L) regulaer ist, kann trivialerweise ueber die Abschlusseigenschaften von regulaeren Sprachen bewiesen werden. Den Hinweis wuerde ich persoenlich nicht verwenden. Darueber hinaus solltest du dich nicht an dem Wort Even festhalten, es haette auch einfach M(L) = {w in L| |w|%2=0} lauten koennen.

    0
  • V

    Danke knivil für deine Antwort.

    Insbesondere das hier hat mir sehr geholfen:

    Darueber hinaus solltest du dich nicht an dem Wort Even festhalten, es haette auch einfach M(L) = {w in L| |w|%2==0} lauten koennen.

    Wie du geschrieben hast konstruiert eine Funktion f(x) eine neue Zahl y. Konstruieren "an sich" tut das ja dann der dahinterliegende Term wie bspw. x^2. Der Term ist in meinem Fall also die Definition davon; also quasi: {w in L | |w|%2 == 0}.

    Das heißt also nun, dass man über die Abschlusseigenschaften argumentieren kann. Even(L) filter also alle Wörter aus der Sprache L, die gerade Wortlänge haben. Welche Abschlusseigenschaften gelten hab ich mittlerweile (auswendig) aus meinem Lehrbuch gelernt. Jetzt stellt sich leider nur noch die Frage welche Abschlusseigenschaft hier zutrifft. Ich denke aber die Schnittmenge sollte hier passen, oder?

    -> L ist laut Aufgabe regulär.
    -> Der Durchschnitt zweier regulärer Sprachen ist regulär.

    Wenn ich nun einen Automaten für die Sprache Lmod={v∈Σ⋆∣∣v∣mod2=0}L_{mod} = \{ v \in \Sigma^{\star} | |v| mod 2 = 0 \} (die regulär ist) erstelle, könnte ich doch nun aus LmodL_{mod} und der aus der Aufgabe gegebenen Sprache LL einen Produktautomaten erstellen, der mir dann Even(L)Even(L) erkennt.

    Stimmt das soweit?

    0
  • K

    Ja, aber konkret kannst du den Produktautomaten nicht angeben, da du erstmal kein konkretes L gegeben hast.

    0
  • V

    Genau. Einen konkreten Produktautomaten kann ich nicht angeben, da kein konkretes L gegeben ist. Soweit hab ich das nun verstanden.

    Danke für eure Hilfe!

    0
Anmelden zum Antworten