Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in END-AC

Beantwortet: RA für EA

Fri, 12 Jan 2018 13:08:20 +0000

Hallo uldvb,

Den regulären Ausdruck den du zum deterministischen endlichen Automat angegeben hast ist auch richtig. Wenn du dir Beispielwörter der definierten Sprache überlegst, wirst du sehen, dass diese durch beide regulären Ausdrücke dargestellt werden können. Der Grund dafür ist, dass du, mit dem Algorithmus aus der Aufgabe, aus einem ndet. EA einen äquivalenten det. EA formen kannst und dementsprechend auch die regulären Ausdrücke gleich sind.

Allgemein ist es jedoch sinnvoller den ndet. EA auszuwählen als Grundlage für einen regulären Ausdruck, da dies meist einfacher ist.

Ich hoffe ich konnte weiterhelfen!

Viele Grüße,

Timon (Tutor)

Beantwortet: Verständnis Zustände

Fri, 24 Oct 2014 09:37:18 +0000

Wenn Ihr nach dem Algorithmus aus der Vorlesung vorgeht, sollte es bei dieser Aufgabe zu keinen Problemen kommen. {s2} geht mit 1 in {s2,s3} und somit logischerweise auch eine Zeile weiter unten {s2,s3}. Man geht nur in die leere Menge wenn keiner der Zustände in der Klammer wohin führt. Dies ist aber nur bei {s1} mit 0 und {s0} mit 1 der Fall.
Gruß Alexander (Tutor)

Beantwortet: Zustand s5 unnötig

Fri, 24 Oct 2014 09:19:12 +0000

Hallo Richard,

nein, diese Annahme ist nicht richtig. Einem deterministischen endlichen Automaten kann jedes Wort aus E* als Eingabe übergeben werden. Erst sobald das Wort "abgearbeitet" ist entscheidet sich, ob das Wort akzeptiert wird oder nicht, nämlich ob der dEA in einem Endzustand stoppt oder nicht. Ich glaube, dass dir das noch nicht ganz klar ist.

Zudem: Bei einem dEA muss in jedem Zustand für jedes Eingabesymbol klar sein, was zu tun ist. Würde man nach deiner Anmerkung also die Kanten Streichen, so wäre dies kein dEA mehr.

Nun eine kurze Erklärung für den Zustand s5:

Dieser Zustand ist eine Art nicht-akzeptierender Sackgassenzustand, d.h. ab hier ist klar, dass - egal welche Eingabe noch kommen mag - das Wort nicht mehr akzeptiert wird. Du erkennst ihn daran, dass er nicht mehr verlassen werden kann (alle Elemente aus E führen wieder in s5) und kein Endzustand ist.

Gruß

Philip (Tutor)

Beantwortet: Warum ist s3 bereits Endzustand?

Fri, 24 Oct 2014 09:17:40 +0000

Hallo,

hinter der letzten 0 steht ein Sternchen, d.h. sie kann beliebig oft, also auch gar nicht vorkommen. Pflichtbestandteil sind lediglich am Anfang eine 0 und eine 1, danach irgendetwas (beliebig viele Nullen oder Einsen oder irgendeine Kombination aus beiden) und danach eine Eins, die Anzahl der Nullen am Schluss kann beliebig sein. Sobald also nach 01... eine weitere 1 auftaucht, ist das Wort gültig. Die schließende Null(en) spielen für die Gültigkeit keine Rolle mehr. Vereinfacht lässt sich sagen: Das Wort muss mit 01 anfangen und danach muss noch irgendwo mindestens eine weitere 1 kommen. Am Ende (nach der "Pflichteins") darf aber noch eine beliebige Zeichenfolge stehen (deswegen die 0* am Ende des regulären Ausdrucks).

MfG, Jakob

Beantwortet: Aufstellung regulärer Ausdruck

Fri, 24 Oct 2014 09:15:22 +0000

Das von dir beschriebene Vorgehen ist ein Ansatz, der häufig funktioniert, aber keineswegs ein allgemeiner Algorithmus, welcher immer zu einem gültigen regulären Ausdruck führt.

Trotzdem ist das Vorgehen hier im Prinzip ohne weiteres auf den nichtdeterministischen Automaten anwendbar. Man formuliert den regulären Ausdruck, der zu einem Endzustand führt; es ergibt sich:

01(0 + 1)*1

es ergi dann schaut man welche Schleifen vom Endzustand wieder zum Endzustand führen, das ist hier nur die 0. Diese wird deshalb mit einem * angehängt.

Gruß,
Jacob (Tutor)