Question

Geben Sie paarweise an, ob die folgenden NFA M1,M2 und M3 die gleiche Sprache akzeptieren. Die akzeptierte Sprache muss nicht explizit angegeben werden.

Comments

Die akzeptierte Sprache muss nicht explizit angegeben werden.

Das würde ich Dir aber empfehlen! Es ist nicht nur eine gute Übung, sondern bietet auch eine geeignete Argumentationsgrundlage. Alternativ könntest Du über einen Regex argumentieren. Vielleicht will der Prof. auch auf eine Automatenüberführung hinaus. Versuche es mal über die Angabe eines Regex und melde Dich wieder, wenn Du nicht weitergekommen bist!

---

Habe mal versucht die Sprachen anzugeben und alles mögliche an Textwörtern da 'durchgejagt' aber ich kann keinen Unterschied erkennen.

Die akzeptierten Sprachen wären doch wie folgt:

M1= (0*1*)*1

M2=0*11*(0*1)*

M3=(00*)*1(00*1)*1*

(Stern= Optional einmal, beliebig oder keinmal)

Alle 3 Automaten akzeptieren doch eine beliebige Folge solange am Ende eine 1 ist.

Denke aber dass es so nicht so ganz richtig ist aber ich finde das nichts...

Answer 1

\(M_1\) akzeptiert alle Wörter über \(\Sigma=\left\{0,1\right\}\), die auf einer \(1\) enden. Das ist auch bei \(M_2\) und \(M_3\) der Fall, weil der Endzustand nur über eine \(1\) erreicht werden kann. Alle Automaten akzeptieren dieselbe Sprache.