Theoretische Informatik NEA und DEA

Question

Aufgabe:

…

L = {w ∈ {a, b} Ι w endet mit abb}

Problem/Ansatz:

… Gebt für die folgende formale Sprache L einen NEA mit
maximal vier Zuständen an, der L erkennt, und berechnet mittels Potenzmengenkonstruktion einen äquivalenten DEA. Benutzt dafür die Vorgehensweise mit der Tabelle, wie sie in der Vorlesung gezeigt wurde.

Answer 1

\(\rightarrow\circ\stackrel{a}{\longrightarrow}\circ\stackrel{b}{\longrightarrow}\circ\stackrel{b}{\longrightarrow}\bullet\)

Einige Transitionen fehlen noch. Die musst du ergänzen. Zum Beispiel

• Was passiert wenn der erste Buchstabe \(b\) ist?
  
• Was passiert wenn bereits \(ab\) gelesen wurde und dann ein \(a\) folgt?
  
• Was passiert wenn bereits \(abb\) gelesen wurde, aber das Wort noch nicht zu Ende ist?
  

Gebt für die folgende formale Sprache L einen NEA mit maximal vier Zuständen an, der L erkennt

In diesem Fall sieht der NEA genau so aus wie der DEA. Das vereinfacht die Potenzmengenkonstruktion enorm :-)