http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0910/FGI2/sec/fgi-a1.pdf

Hi!
Kann mir jemand sagen, in welcher Form die Aufgaben 1.2 und 1.6 gelöst werden sollen?
"Gib eine Konstruktionsvorschrift an" verstehe ich eigentlich so, dass man den gesuchten NFA inklusive des kompletten 5-Tupels angibt. Ich wüsste jetzt aber nichtmal, wie das für den DFA geht, den man per Potenzautomat erhält.

MfG

Also ich habe mir für 1.6. überlegt, dass wenn L(A) = L(B) ist, muss ja gelten, dass L(A) Teilmenge von L(B) ist und umgekehrt.
Dann hab ich mir gedacht, dass ich dies ja auch schön mengentheoretisch ausdrücken kann.

Als nächstes habe ich gedacht, die beiden Automaten also mit Hilfe der Mengenlehre in o.g. Beziehung zu setzen und an die Abfrage nach der Teilmenge weiterzugeben, die mir dann liefert, ob die Sprachen gleich sind oder nicht.

Kann man das so machen?

Zu 1.2. kann ich nichts sagen, hab ich mir noch nicht angeguckt. Allerdings frage ich mich, ob ich da nicht eine allgemeine Form zur Erstellung eines Potenzautomaten angeben soll…

btw: Kann man hier Latex-Code einfügen? Also nicht als Bild oder so, sondern einfachen Code?

Als nächstes habe ich gedacht, die beiden Automaten also mit Hilfe der Mengenlehre in o.g. Beziehung zu setzen und an die Abfrage nach der Teilmenge weiterzugeben, die mir dann liefert, ob die Sprachen gleich sind oder nicht.

Sorry, ich meine natürlich die Abfrage nach der leeren Menge :)

btw: Kann man hier Latex-Code einfügen? Also nicht als Bild oder so, sondern einfachen Code?

Ja, mit [ latex ] hierdeincode [/ latex ]

Ich hab hier mal nen Regulären Ausdruck ;):

(c* + c* a ((ε + c) + b c* a)* b c*) + c* a ((ε + c) + b c* a)* a ((ε + c) + b ((ε + c) + b c* a)* a)* b ((ε + c) + b c* a)* b c*

kann mir iwer tipps geben ob und wie ich das noch vereinfachen kann ?

Danke =)

Ich hab hier mal nen Regulären Ausdruck ;):

(c* + c* a ((ε + c) + b c* a)* b c*) + c* a ((ε + c) + b c* a)* a ((ε + c) + b ((ε + c) + b c* a)* a)* b ((ε + c) + b c* a)* b c*

kann mir iwer tipps geben ob und wie ich das noch vereinfachen kann ?

Danke =)

Einmal können die fett markierten Klammern weggelassen werden. Zweitens die markierten ε, weil ε in <irgendwas>* bereits enthalten ist.

Irgendein regulärer Ausdruck konkateniert mit der leeren Menge ist die leere Menge oder?
Irgendein regulärer Ausdruck vereinigt mit der leeren Menge ist? Auch die leere Menge?

Irgendein regulärer Ausdruck konkateniert mit der leeren Menge ist die leere Menge oder?
Irgendein regulärer Ausdruck vereinigt mit der leeren Menge ist? Auch die leere Menge?

Alles falsch.
Google besser nochmal nach Mengenlehre.

Irgendein regulärer Ausdruck konkateniert mit der leeren Menge ist die leere Menge oder?

Korrekt. Denn die Konkatenation der Menge A mit der Menge B bedeutet alle Elemente aus A mit allen Elementen aus B zu konkatenieren, und wenn [latex]B = \emptyset [/latex] bedeutet dies alle Elemente aus A mit keinem Element zu konkatenieren.

Irgendein regulärer Ausdruck vereinigt mit der leeren Menge ist? Auch die leere Menge?

Nein, bei der Vereinigung gehen keine Elemente "verloren". Das Resultat ist in dem Fall die Menge die du durch den regulaeren Ausdruck beschreibst.

Hab ich ja :o

Die Menge der Wörter einer formalen Sprache kann endlich oder unendlich sein, wobei dann auch der Begriff einer endlichen bzw. unendlichen (formalen) Sprache verwendet wird. Wenn die Menge der Wörter der formalen Sprache gleich der leeren Menge ist, spricht man auch von der leeren Sprache. Die Sprache, die nur das leere Wort enthält, ist selbst nicht leer, sondern einelementig.

Das absorbierende Element der Konkatenation ist die leere Sprache, so dass für jede Sprache L [latex]\in \Sigma^*[/latex] gilt:

[latex]L \circ \{ \} = \{ \} \circ L = \{ \} [/latex]

______________
Edith sagt Danke

Ich hab hier mal nen Regulären Ausdruck ;):

(c* + c* a ((ε + c) + b c* a)* b c*) + c* a ((ε + c) + b c* a)* a ((ε + c) + b ((ε + c) + b c* a)* a)* b ((ε + c) + b c* a)* b c*

kann mir iwer tipps geben ob und wie ich das noch vereinfachen kann ?

Danke =)

Einmal können die fett markierten Klammern weggelassen werden. Zweitens die markierten ε, weil ε in <irgendwas>* bereits enthalten ist.

NEIN, so einfach geht das nicht:
c* a (ε + c) beschreibt die Menge [latex]\{c\}^*\{a\} \cup \{c\}^*\{a\}\{c\}[/latex]
aber
c* a c nur die andere Menge [latex]\{c\}^*\{a\}\{c\}[/latex]

aber "ausmultiplizieren" hilft zunächst meist weiter.

Nur mal so am Rande.

Ist eigentlich überall mit + Vereinigung, sprich [latex]\cup[/latex] gemeint?

Mich verwirrt das etwas wenn im FGI 1 Skript Formel mit [latex]\cup[/latex] geschrieben wird und jetzt mit "+".

Nur mal so am Rande.

Ist eigentlich überall mit + Vereinigung, sprich [latex]\cup[/latex] gemeint?

Mich verwirrt das etwas wenn im FGI 1 Skript Formel mit [latex]\cup[/latex] geschrieben wird und jetzt mit "+".

+ wird  fuer regulaere Ausdruecke verwendet
[latex] \cup [/latex] fuer Mengen.

regulaere Ausdruecke beschreiben Mengen, sind aber selbst keine Mengen!
Also [latex] c^* \neq \lbrace c \rbrace^* [/latex]

@theorinix: Wirklich? Da ist noch ein Klammernpaar, welches das ganze "sternt", so das das Epsilon weggelassen werden kann:
[latex]
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[ngerman]{babel}
\begin{document}
\(c^* + c^* a \textbf{(}(\varepsilon + c) + b c^* a\textbf{)}^*bc^* = c^* + c^* a (c + b c^*a)^*bc^*\)
\end{document}
[/latex]

kann man aus a(b+c)* = ab*+ac* machen?

kann man aus a(b+c)* = ab*+ac* machen?

Nein. Z.B. ist das Wort abc auf der linken Seite enthalten aber nicht auf der rechten.

Also, vereinfachen kann man das ganze noch erheblich, Dienstag kann ich hier auch meine Lösung schreiben. Bis dahin habt ihr ja noch Zeit mit dem Abgeben :)

Mir sind kaum brauchbare Regeln und keine Algorithmen bekannt, wie man so einen Ausdruck vereinfachen kann. Falls da jemand was tolles hat, nur her damit!

Ich hab hier mal nen Regulären Ausdruck ;):

(c* + c* a ((ε + c) + b c* a)* b c*) + c* a ((ε + c) + b c* a)* a ((ε + c) + b ((ε + c) + b c* a)* a)* b ((ε + c) + b c* a)* b c*

kann mir iwer tipps geben ob und wie ich das noch vereinfachen kann ?

Danke =)

Einmal können die fett markierten Klammern weggelassen werden. Zweitens die markierten ε, weil ε in <irgendwas>* bereits enthalten ist.

NEIN, so einfach geht das nicht:
c* a (ε + c) beschreibt die Menge [latex]\{c\}^*\{a\} \cup \{c\}^*\{a\}\{c\}[/latex]
aber
c* a c nur die andere Menge [latex]\{c\}^*\{a\}\{c\}[/latex]

aber "ausmultiplizieren" hilft zunächst meist weiter.

Der Ausdruck ist aber nicht c* a (ε + c), sondern

…+ c* a ((ε + c) + b c* a)* b c*) +…

wobei man bei ((ε + c) + b c* a)* aufgrund der sternbildung ε weglassen kann. Analog bei den anderen Teilausdrücken.

@theorinix: Wirklich? Da ist noch ein Klammernpaar, welches das ganze "sternt", so das das Epsilon weggelassen werden kann:
[latex]
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[ngerman]{babel}
\begin{document}
\(c^* + c^* a \textbf{(}(\varepsilon + c) + b c^* a\textbf{)}^*bc^* = c^* + c^* a (c + b c^*a)^*bc^*\)
\end{document}
[/latex]

Ich bezog mich nur auf die falsche Aussage "… [latex]\varepsilon[/latex] kann weggelassen werden, weil
[latex]\varepsilon[/latex] in <irgendwas> enthalten ist." Da stand nix von dem Stern!

Da steht schon: "weil ε in <irgendwas>* bereits enthalten ist." Aber wir wollen ja keine Erbsen zählen…

Da steht schon: "weil ε in <irgendwas>* bereits enthalten ist." Aber wir wollen ja keine Erbsen zählen…

Oh, ich habe das klitzekleine Sternchen nicht erkannt, meine Augen machen das selbst mit Brille kaum mit!
Sorry, ich sollte mich besser zurückhalten…

Oh, ich habe das klitzekleine Sternchen nicht erkannt, meine Augen machen das selbst mit Brille kaum mit!
Sorry, ich sollte mich besser zurückhalten…

Och nö, theorinix, lieber nicht zurückhalten und weiter mitlesen und vor allem -helfen. Missverständnisse wie das obige können ja passieren und klären sich meist recht schnell. Die fachliche Qualifikation wird deshalb sicher auch nicht angezweifelt. Ich persönlich hätte hier gern mehr theorinixe gesehen.

Och nö, theorinix, lieber nicht zurückhalten und weiter mitlesen und vor allem -helfen. Missverständnisse wie das obige können ja passieren und klären sich meist recht schnell. Die fachliche Qualifikation wird deshalb sicher auch nicht angezweifelt. Ich persönlich hätte hier gern mehr theorinixe gesehen.

Find ich auch. Bitte bitte nicht zurückhalten :)

vote theorinix 4 president!

1.4.2
Hat da jemand einen Ansatz? Das wurde in meiner Übungsgruppe leider förmlich überflogen (der Präsenz Teil) und ich weiß jetzt nicht was da gewollt ist.
Was ist genau mit Inklusion gemeint?
Induktion Ja/Nein?

1.4.2
Hat da jemand einen Ansatz? Das wurde in meiner Übungsgruppe leider förmlich überflogen (der Präsenz Teil) und ich weiß jetzt nicht was da gewollt ist.
Was ist genau mit Inklusion gemeint?
Induktion Ja/Nein?

Inklusion hat erstmal nichts mit Induktion zu tun.
Inklusion meint nur dass die Menge A in der Menge B enthalten ist, also dass die [latex]A \subseteq B[/latex] ist. Die Inklusion ist echt, wenn [latex] A \neq B [/latex] gilt, also wenn A eine echte Teilmenge ist (B zumindest ein Element enthaelt was A nicht enthaelt, wird auch [latex]A \subsetneq B[/latex] notiert).

Die Aufgabe laesst sich definitiv ohne vollstaendige Induktion loesen!

Das absorbierende Element der Konkatenation ist die leere Sprache, so dass für jede Sprache L [latex]\in \Sigma^*[/latex] gilt:

[latex]L \circ \{ \} = \{ \} \circ L = \{ \} [/latex]

Kann man das so einfach auf unsere Mengen übertragen? Ich nehme an JA, dann habe ich aber ein Problem:

Und zwar ist dann zum Beispiel [latex]R^1_{1,3} = \emptyset + \emptyset \cdot (\epsilon + c)^{*} \cdot a=\emptyset[/latex] bzw. korrekter gesagt der reguläre Ausdruck, der die leere Menge akzeptiert. Wenn ich mich recht erinnere, meint aber [latex]R^1_{1,3}[/latex] den regulären Ausdruck, der alle Wörter akzeptiert, die von Zustand 1 in Zustand 3 führen und dabei 1 Zwischenzustand verwenden. Wenn ich mir den Automaten so anschaue, müsste also [latex]R^1_{1,3} = a c^{*} a[/latex] sein. Leider komme ich mit der Formel zur Kleene-Konstruktion aber wie gesagt auf die leere Menge.

Kann mir bitte jemand sagen, wo mein Fehler liegt?

du hast alles richtig erläutert, nur übersehen das zwischen der 1 und der 3 noch die 2 liegt.

Allerdings ist R1,1,3 = Ø + (e + c)(e + c)* Ø  = Ø

Wenn ich mich recht erinnere, meint aber [latex]R^1_{1,3}[/latex] den regulären Ausdruck, der alle Wörter akzeptiert, die von Zustand 1 in Zustand 3 führen und dabei Zustand 1 als Zwischenzustand verwenden.

hier war der fehler.

[offtopic]

vote theorinix 4 president!

Nur zu welchem? Womöglich ist er das bereits [7]
[/offtopic]

vote theorinix 4 president!

Danke, aber das wäre wohl zu viel der Ehre…
und noch mehr Verpflichtung wäre das dann auch noch.
Eher nix für theorinix.

Das absorbierende Element der Konkatenation ist die leere Sprache, so dass für jede Sprache L [latex]\in \Sigma^*[/latex] gilt:

[latex]L \circ \{ \} = \{ \} \circ L = \{ \} [/latex]

[…]

@s4ms3milia:
Was meinst Du mit [latex]L \circ M[/latex] bei Mengen? Konkatenation gibt es nur bei Wörtern und nicht bei Mengen, auch normalerweise nicht bei Mengen von Wörtern! Dazu hatte man in FGI-1 das Komplexprodukt benutzt, welches dann so interpretiert wird:
[latex]L \cdot M := \{x\odot y \mid x\in L \land y\in M\}[/latex]. Dabei gilt [latex]L,M\subseteq H[/latex] f"ur ein Monoid (oder eine Halbgruppe) [latex](H,\odot)[/latex].
Wenn für [latex] \odot[/latex] die Konkatenation gewählt wird, sehen wir, warum die Antwort von 4ms3milia im Wesentlichen richtig war.

Ich hab hier mal nen Regulären Ausdruck ;):
(c* + c* a ((ε + c) + b c* a)* b c*) + c* a ((ε + c) + b c* a)* a ((ε + c) + b ((ε + c) + b c* a)* a)* b ((ε + c) + b c* a)* b c*
kann mir iwer tipps geben ob und wie ich das noch vereinfachen kann ?

(c+a(c+ac*b)*b)*
Ist das die richtige Lösung? Wie kommt man auf formalem Wege dorthin?

Mit dem Verfahren von Kleene, welches auch auf dem Zettel erwähnt wird. Dann kommt so ein hübscher ellenlanger term heraus.
Deine Lösung (c+a(c+ac*b)*b)* bezweifel ich einfach mal, keine ahnung wo die herkommt?

Hab ich mir ausgedacht.
Zumindest auf Worten bis Länge 16 stimmen beide regex überein.
Meine Frage war, wie man von der langen, durch Kleene generierten Version, auf meine kurze kommen könnte.

Hab ich mir ausgedacht.
Zumindest auf Worten bis Länge 16 stimmen beide regex überein.
Meine Frage war, wie man von der langen, durch Kleene generierten Version, auf meine kurze kommen könnte.

Klammern ausmultiplizieren und geschicktes Zusammenfassen.
[latex](\{\epsilon\}\cup M)^+ = M^* [/latex]
u.a. verwenden.
Aber das Eergebnis kommt nur heraus, wenn's denn auch stimmt!
Mit dem Original (Automat?) beginnen wäre hilfreich, ich kernne den ja nicht, und das andere schrieb ich bereits etwas früher.

Es ist ein Automat.
Startzustand = Endzustand.
An jedem zustand ist ein c-kringel.
Über a kommt man zum nächsten Zustand und über b zurück.

Ich hab hier mal nen Regulären Ausdruck ;):
(c* + c* a ( (ε + c) + b c* a)* b c*) + c* a ((ε + c) + b c* a)* a ((ε + c) + b ((ε + c) + b c* a)* a)* b ((ε + c) + b c* a)* b c*
kann mir iwer tipps geben ob und wie ich das noch vereinfachen kann ?

(c+a(c+ac*b)*b)*
Ist das die richtige Lösung? Wie kommt man auf formalem Wege dorthin?

(c* + c* a ( (ε + c) + b c* a)* b c*)  + …

ist der erste "Summand" von Phillips Regex.
Er beschreibt eine Menge, in der das Wort cab enthalten ist.
Das Wort cab ist aber in deinem Regex (c+a(c+ac*b)*b)* nicht enthalten!

Das Wort cab ist aber in deinem Regex (c+a(c+ac*b)*b)* nicht enthalten!

doch, ist drin.

Das Wort cab ist aber in deinem Regex (c+a(c+ac*b)*b)* nicht enthalten!

doch, ist drin.

Hast recht, sorry :)