Ersetzung und Automaten (Regularität)

• Normalformen
  • Normalformen für {fgfg$\to$...}?
  • Normalformen für {A(A(D, x), y)$\to$...}?
  • Ist Menge der Normalformen immer regulär? (Nein.)
• Nachfolgermengen
  • L und E durch endliche (Baum-)Automaten beschrieben. Wie kann man R^*(L) $\cap$ E = $\emptyset$ entscheiden?
  • im Allgemeinen gar nicht, wg. Halteproblem
  • in Einzelfällen doch

    $\Sigma$ = {a, b}, R = {aa$\to$aba}, L = a^*, E = $\Sigma^{*}_{}$bb$\Sigma^{*}_{}$