2.3

[W.E.]

Weiss jemand wie man die Differenz bei diesem Beispiel angibt?

Ist {a,b,c}*= epsilon,abc,abcabc,abcabcabc,... oder ist das auch epsilon,a,ab,aa,abb,acc,abc,... (was ich nicht glaube)

Und wie soll ich dann das {abc} abziehen bzw. wie stellt man das dar?

[spjoe]

Ist {a,b,c}*= epsilon,abc,abcabc,abcabcabc,... oder ist das auch epsilon,a,ab,aa,abb,acc,abc,... (was ich nicht glaube)

ich glaube zweiteres ist richtig

automat hab ich noch nicht überlegt

[W.E.]

Ich denke eben nicht.

Das wär dann ja {a}*{b}*{c}* oder? Oder ist dann dass dasselbe?

[axestr]

{a,b,c}* - {abc} ist alles was man inkl. Epsilone mit den drei buchstaben machen kann, ausser abc.
{a}*{b}*{c}* währen beliebig viele a gefolgt von beliebig viele b gefolgt von beliebig vielen c. Damit kann man aber z.B. cba nicht darstellen, was man mit {a,b,c}* - {abc} aber schon kann.
Es gilt ja auch A*=A**, also ist {a,b,c}* - {abc} = {a,b,c}*{a,b,c}* - {abc} = {a,b,c}*{a,b,c}*{a,b,c}* - {abc} .....
Für den Automaten braucht man eine Falle.
(q0)-(q1)-(q2)-(Falle).
q0 ist start und Endzustand, q1,q2 sind auch Endzustände.
q0,a=q1
q1,b=q2
q2,c=Falle
Sonnst geht alles zurück nach q0 (ausser von der Falle)
Also
q0,b=q0
q0,c=q0
q1,a=q0
q1,c=q0
q2,a=q0
q2,b=q0
Glaube das müsste so gehen.
Lg, Axel.

[rinf]

Aber fehlt nicht noch das \epsilon ?

[axestr]

Der Automat ist sowieso falsch, weil er z.B. aabc nicht akzeptiert ;-)

(q0)-(q1)-(q2)-(q3)-((q4))

q0,a = q1
q0,!=a = q4
q1,b = q2
q1,!=b = q4
q2,c = q3
q2,!=c = q4
q4,beliebig = q4

Startzustand ist q0, Endzustand q4.

Stimmt das jetzt? Irgendwie ist das ohne Aufzeichnen nicht so leicht ;-)

Lg, Axel.

[spjoe]

jo zeichnung hab ich eine weiss aber net ich die posten soll

A=\left\{Q,\Sigma,\delta,q_0,F\right\}
Q=\left\{q_0,q_1,q_2,q_3,q_4\right\}
\Sigma=\left\{\underline{a},\underline{b},\underli ne{c}\right\}
q_0=q_0
F=\left\{q_0,q_1,q_2,q_4\right\}

\delta=
\begin{pmatrix} & \underline{a} & \underline{b} & \underline{c}\\ q_0 & q_1 & q_4 & q_4 \\ q_1 & q_4 & q_2 & q_4 \\ q_2 & q_4 & q_4 & q_3\\ q_3 & q_4 & q_4 & q_4\\ q_4 & q_4 & q_4 & q_4\end{pmatrix}

[spjoe]

beim endknoten ist auch ne schleife sieht man aber schlecht (kenn mich mit dem violet uml editor net wirklich gut aus)

[raymond]

aber deine uebuengfunktion kann nicht bekommen werden: a,ab

[rinf]

sind bei mir auch endknoten. das dritte kästchen kann man auch weglassen, oder?

weiß jemand, ob man das \epsilon extra berücksichtigen muss?

[spjoe]

aber deine uebuengfunktion kann nicht bekommen werden: a,ab
stimmt, aber einfach q1 und q2 als endknoten definieren und es passt

[raymond]

Das glaube ich auch!

[raymond]

wenn man das beispiel machen wird,was zuerst ueberlegen?

[michi86m]

bei epsilon müsste q0 gleichzeitig ein endpunkt sein oder?

[mike_32]

stimmt, aber einfach q1 und q2 als endknoten definieren und es passt

hi !!
hätte eine frage zu deinem automat.
es ist ja möglich bca abc || abc abc alle diese möglichkeiten dürten nicht möglich sein da abc 1mal abgezogen werden sollte oder verstehe ich die sache falsch?

lg
michi

[freeye]

warum nicht einfach mit 3 zuständen, q0, q1, q2

q0 = startzustand + endzustand
mit q0,a,b,c -> q1
und q1,a,b,c -> q2 (endzustand)
q2, a,b,c -> q2


dadurch is gewährleistet, dass nie a, b oder c alleine sind, sonst ist ja alles erlaubt..

edit: q0 = endzustand auch, damit klappt jetzt alles, denk ich

[thoreon]

Hallo,

Doch diese Möglichkeiten dürfen vorkommen, nur exakt die Zeichenfolge "abc" darf nicht vorkommen.

z.B. darf "abca" "abcabc" "babcc" usw. vorkommen.
Deshalb auch die Verbindung des q3 nach q4.

Hoffe das klingt verständlich...

Lg
Thomas

[thoreon]

@ freeye:
Bei deinem Vorschlag akzeptierst du aber die Zeichenfolge "abc" und die darf eben NICHT akzeptiert werden.
Es geht nicht um die einzelnen Symbole a, b oder c sondern um die Zeichenkette "abc" --> da sind keine Beistriche dazwischen ;-)

Lg
Thomas

[tonico]

Hi,

Ich möchte bei dem Beispiel nach Kochrezept vorgehen, also

Angabe als reguläre Menge darstellen,
aus der reguläre Menge einen NEA konstruieren,
aus dem NEA einen DEA konstruieren und
den DEA minimieren.

Nur scheitere ich schon beim ersten Punkt, weiß jemand wie man die Angabe als reguläre Menge darstellen kann?

[tonico]

Für die Nachwelt, hier die reguläre Menge zu diesem Automaten mit L={a,b,c}:

{b,c}L* U {a}{a,c}L* U {ab}{a,b}L* U {abc}{a,b,c}L*
b... aa... aba... abca...
c... ac... abb... abcb...
abcc...

[da_pat]

jo zeichnung hab ich eine weiss aber net ich die posten soll

A=\left\{Q,\Sigma,\delta,q_0,F\right\}
Q=\left\{q_0,q_1,q_2,q_3,q_4\right\}
\Sigma=\left\{\underline{a},\underline{b},\underli ne{c}\right\}
q_0=q_0
F=\left\{q_0,q_1,q_2,q_4\right\}

\delta=
\begin{pmatrix} & \underline{a} & \underline{b} & \underline{c}\\ q_0 & q_1 & q_4 & q_4 \\ q_1 & q_4 & q_2 & q_4 \\ q_2 & q_4 & q_4 & q_3\\ q_3 & q_4 & q_4 & q_4\\ q_4 & q_4 & q_4 & q_4\end{pmatrix}
hallo!

ich hab zwei fragen.

was heißt der ausdruck in der klammer von sigma?
zu delta: warum kommt man von q3 bei beliebiger eingabe zu q4?

mfg

[marioana]

was in der angabe mit 5-tupel gemeint?
hier steht ja "beschreiben sie A sowohl durch einen graphen als auch durch ein 5-tupel"
das heißt man soll den DEA zeichen und weiter....?

[tonico]

was in der angabe mit 5-tupel gemeint?
hier steht ja "beschreiben sie A sowohl durch einen graphen als auch durch ein 5-tupel"
das heißt man soll den DEA zeichen und weiter....?

Das ist nichts anderes als das Tupel <Q, Σ, δ, q0, F>.
Q...Menge der Startzustände
Σ...das Alphabet
δ...die Übergangsfunktion
q0...der Startzustand
F...Menge der Endzustände

Noch ein Tipp: man kann den Automaten erstellen in dem man zuerst einen Automaten erstellt der nur "abc" akzeptiert und anschließend einfach Start- und Endzustände vertauscht.

[kefalo]

soll automat auch wort "aaabc" und nicht nur "abc" falsch anzeigen(falle)???

bei mir es ist alles gut bis er "abc" liest, dann geht der leser in falle. es sollte egal sein was vor abc kommt(xxxxxxxabc) das eingelesene wort gehort nicht zu der sprache. stimmt das?

[axestr]

soll automat auch wort "aaabc" und nicht nur "abc" falsch anzeigen(falle)???
bei mir es ist alles gut bis er "abc" liest, dann geht der leser in falle. es sollte egal sein was vor abc kommt(xxxxxxxabc) das eingelesene wort gehort nicht zu der sprache. stimmt das?

{a,b,c}* - {abc} ist alles was man mit a,b,c bilden kann, ausser dem Wort
"abc". Also sind insbesondere "aabc" und "abcc" akzeptierte Wörter. Nachdem "aaabc" und "xxxxxxxxxxxxxabc" (unter der Vorraussetzung das x ungleich Epsilon ist) nicht gleich "abc" sind gehören also auch zur Sprache.

Lg, Axel

[kefalo]

Danke! :)

[tonico]

soll automat auch wort "aaabc" und nicht nur "abc" falsch anzeigen(falle)???

bei mir es ist alles gut bis er "abc" liest, dann geht der leser in falle. es sollte egal sein was vor abc kommt(xxxxxxxabc) das eingelesene wort gehort nicht zu der sprache. stimmt das?

Nein stimmt nicht, der Atomat soll alle Wörter aus {a,b,c}* akzeptieren außer genau das eine Wort "abc". Schau Dir mal den Tipp in Posting #23 an.