Reguläre Sprachen. Existiert mindestens ein DEA M?

Question

Sei L eine reguläre Sprache über dem Alphabet Σ. Zeigen Sie dass ein DEA M existiert, mit:



i) L(M) = L, und

ii) Σ ist das Eingabealphabet zu M.



(Hinweis: Die Regularität von L sagt direkt nur, dass es einen DEA M´ existiert, mit L(M´ ) = L. Es ist aber möglich, dass M´ ein Eingabealphabet Σ´ benutzt, mit Σ´ ≠ Σ, und dann reicht M´ nicht.)

Answer 1

Wenn a ∈ Σ\Σ' ist, dann kann ein Zustand hinzugefügt werden, der beim Lesen von a das Eingabewort verwirft.

Wenn a ∈ Σ'\Σ ist, dann können die dazu passenden Übergänge entfernt werden.

In beiden Fällen enthält L keine Wörter in denen a vorkommt.