Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in END-AC

Bearbeitet: RA für EA

Tue, 23 Jan 2018 19:56:11 +0000

von der gegebenen RA bzw. 01(0+1)*10* habe ich nEA A entwickelt und dann EA A´, aber ietzt nehme ich an, dass A´ als eine Frage geben ist, und ist verlangt ein RA für A´ zu schreiben, dann werde ich auf jeden Fall schreiben 01(0)*1(0+1)*.

woran liegt dieser Unterschied? oder beide sind gleich?

@[latex: %varm|gra% @{regex:01(0+1)*10*}@ \\
\noindent @{regex:01(0)*1(0+1)*}@]@

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)

Kommentiert: Zustand s5 unnötig

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

Danke Philip,

das hat mir für das Verständnis weiter geholfen. Ich dachte es wäre ausreichend nur zu definieren, welche Schritte erlaubt sind. Sofern ein Schritt nicht definiert ist und der gemacht werden soll, dass dann klar ist, das es nicht erkannt werden kann. Aber so wie du es sagst, muss ich dem EA immer zeigen was er machen soll in den jeweiligen Zustand, auch wenn er dadurch in eine "Sackgasse" kommt.

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)