Automatenbeweis

[vip*r]

Aufgabe

Sei $L \subseteq \Sigma^{\star}_{\text{Bool}}$ eine reguläre Sprache. Beweisen oder widerlegen Sie die folgende Aussage

$Even(L) = \{ w \in L | \left| w \right| \text{mod2} = 0 \} |$ ist regulär

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

Also, einen Automaten zu bauen der die Sprache $\left| w \right| \text{mod2} = 0$ erkennt, ist ja jetzt nicht ganz so schwierig. Aber ich verstehe nicht was mit Even(L) gemeint ist. Hat da von euch jemand Ahnung?

Und noch kurz zum Beweis: Ab dem Zeitpunkt wo ich weiß, was mit Even(L) gemeint ist, kann man ja den Automat zeichnen und je nachdem ob man ihn zeichnen kann oder nicht, hat man in widerlegt, oder eben bewiesen. So sollte das doch funktionieren, oder?

Edit: Hab den mod-2-Automaten vergessen:

q0 -(0)-> q0
q0 -(1)-> q1
q1 -(0)-> q0
q1 -(1)-> q1

q0 ist akzeptierend un Startzustand.

[knivil]

Also, einen Automaten zu bauen der die Sprache |w|mod2=0 erkennt, ist ja jetzt nicht ganz so schwierig.

Fuer dich vielleicht schon.

Aber ich verstehe nicht was mit Even(L)

Steht doch auf der rechten Seite. Menge aller Woerter aus L mit gerader Laenge.

Beweisen oder widerlegen Sie die folgende Aussage

Trivial, da der Schnitt zweier regulaerer Sprachen wieder regulaer ist. Siehe Abschlusseigenschaften. Der Automat fuer Even(L) wird nicht benoetigt. Du musst nur zeigen, dass |w| mod 2 == 0 eine regulaere Sprache ist. Was bedeutet Even(L) genau. Also w in L und |w| mod 2 == 0. Also L' = (w mit w in L und |w|mod 2 == 0}, also L' = {w in L} und {|w|mod 2 == 0}. Und das ist der Schnitt zweier Mengen.

Hab den mod-2-Automaten vergessen

Er ist falsch. |w| bedeutet Laenge des Wortes. Weil: w = '0' wird akzeptiert, hat aber Laenge eins.

Edit: Das hat mich 5 Minuten gekostet (und ich hatte Theoretische Informatik vor 11 Jahren). Sollte das fuer dich laenger Dauern, sehe ich schwarz fuer die Klausur in theoretischer Informatik. Vorlesungen nacharbeiten, mehr ueben, mehr alleine machen, mehr mit den anderen reden ...

[vip*r]

Ich soll also L' = L_a und L_b = {w in L} und {|w|mod 2 == 0} angeben.

Das heißt, ich muss einen Produktautomaten machen, der aus L_a und L_b besteht? Die Vereinigung der akzept. Zustände beider Sprachen gibt mir dann die akzept. Zustände von L' an, womit ich dann Even(L) bewiesen hätte?

Das mein mod-Automat falsch war, weiß ich nun auch. Ich hab irgendwie die "Betragstriche" nicht gesehen. Mir ist schon klar, dass damit die Wortlänge gemeint ist. Der Automat den ich gezeichnet hab, hat den Zahlwert mod2=0 berechnet.

[knivil]

Ich soll also L' = L_a und L_b = {w in L} und {|w|mod 2 == 0} angeben.

NEIN!

ich muss einen Produktautomaten machen

Steht da etwa: Wie lautet der Produktautomat? NEIN!

Wie sollst du einen Automaten von einer regulaeren Sprache L angeben, die du nicht kennst? ALSO: Was ist die Aufgabenstellung?

[Bashar]

vip@r schrieb:

Sei $L \subseteq \Sigma^{\star}_{\text{Bool}}$ eine reguläre Sprache. Beweisen oder widerlegen Sie die folgende Aussage

$Even(L) = \{ w \in L | \left| w \right| \text{mod2} = 0 \} \}$ ist regulär

Aber ich verstehe nicht was mit Even(L) gemeint ist. Hat da von euch jemand Ahnung?

In der Aufgabe steht doch eine Definition für Even(L). Was genau verstehst du denn daran nicht?

Und noch kurz zum Beweis: Ab dem Zeitpunkt wo ich weiß, was mit Even(L) gemeint ist, kann man ja den Automat zeichnen

Wahrscheinlich nicht, da es nicht um eine feste Sprache geht, sondern um eine Operation auf einer Sprache. Du kannst also nur beschreiben, wie man aus einem gegebenen Automaten für L eine Automaten für Even(L) konstruieren kann.

und je nachdem ob man ihn zeichnen kann oder nicht, hat man in widerlegt, oder eben bewiesen. So sollte das doch funktionieren, oder?

Dass man den Automaten nicht "zeichen" kann ist aber kein Beweis, das kann ja auch persönliches Unvermögen sein.

[vip*r]

$Even(L) = \{ w \in L | \left| w \right| \text{mod2} = 0 \} |$

Ich weiß nicht was mit Even() gemeint ist. Was heißt das?

Wenn es $L = \{ w \in L | \left| w \right| \text{mod2} = 0 \} |$ heißen würde, dann glaub ich hab ich verstanden was gemeint ist. Dann besteht die Sprache L einfach aus allen Wörtern für die gilt, dass Wortlänge von w mod 2 gleich 0 sein muss.

Aber was macht da jetzt das Even(). Das ist doch eine Funktion. Was macht die?

[Bashar]

vip@r schrieb:

$Even(L) = \{ w \in L | \left| w \right| \text{mod2} = 0 \} |$

Ich weiß nicht was mit Even() gemeint ist. Was heißt das?

Das wird doch mit dieser Zeile definiert!

Ich nehm das jetzt mal auseinander, in der Hoffnung, dass du gerade nur ein bisschen vernagelt bist, aber sonst eigentlich Formeln lesen kannst (sonst weißt du, wo du Nachholbedarf hast.)

Even ist eine Funktion, die jede reguläre Sprache in eine andere Sprache überführt. Also wenn L eine reguläre Sprache ist, dann ist Even(L) irgendeine andere Sprache. Even(L) ist dabei (s.o.) als die Teilmenge von L definiert, die alle Wörter aus L enthält, deren Länge durch 2 teilbar ist.

Die Frage, die du beantworten sollst: Ist diese Sprache Even(L) regulär?

Wenn es $L = \{ w \in L | \left| w \right| \text{mod2} = 0 \} |$ heißen würde, dann glaub ich hab ich verstanden was gemeint ist.

Unwahrscheinlich, das ist ein sinnloser Ausdruck, da L mit sich selbst definiert wird.

[knivil]

Even(L) ist eine Menge parameterisiert durch den Parameter L. Anderes Beispiel: Greater(n) = { x in N | x > n}. Bedeutet: alle natuerlichen Zahlen groesser n. Will man eine konkrete Menge haben, dann wird eingesetzt. Greater(10) waere dann die Menge der natuerlichen Zahlen groesser 5. Sie ist verschieden von Greater(10). Nun muss die Ausgangsmenge nicht N sein. Nennen wir sie mal A = { x in N | x mod 2 == 0 }. Was ist nun die Greater'(n) = { x in A | x > n }?