hallo, sind die folgenden ausdrücke äquivalent? wer kann mir helfen?
0*11*0(0+1)* = (0+1)*10(0+1)*
ist ein regulärere ausdruck zu einem dfa, der die teilzeichenreihe 10 beinhalten muss.
danke
Hallo,
0*11*0(0+1)* = (0+1)*10(0+1)*
Ich vermute mal, dass du mit ‚+‘ ein Oder und mit ‚*‘ ein „beliebig oft (auch nullmal)“ meinst.
ist ein regulärere ausdruck zu einem dfa, der die
teilzeichenreihe 10 beinhalten muss.
Das ist der zweite Ausdruck auf jeden Fall. Beim ersten glaube ich auch, das ist aber nicht so trivial zu sehen. Aber soweit ich das beurteilen kann stimmt der auch.
Wobei der erste Ausdruck wirklich zu einem DFA gehört, der zweite zu einem NDFA (Wenn das erste Zeichen eine 1 ist, weiß der Automat nicht, obs zur ersten oder zur zweite Eins gehört, die im Ausdruck vorkommt).
Grüße,
Moritz
Hi Moritz,
also ich hab mal zu beiden Ausdrücken den Nfa hingeschrieben und dann umgewandelt, es ergibt den gleichen dfa…also müsste es dann tatsächlich äquivalent sein.
Malw as anderes…wenn zwei zuständen in einem dfa akzeptierend sind können sie ja äquivalent sein, müssen aber nicht oder? also wennd er eine akzeptierende zustand von den vorigen nicht akzeptierenden erreicht wird und NUR von dem akzeptierenden weitere pfeile gehen zu akzeptierenden, also quasi sinnlose, denn von akzeptierenden in akzeptierenden müsste ja heißen äquivalent…?!
blickst noch durch?
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]