0 Daumen
123 Aufrufe

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.)

von

1 Antwort

0 Daumen

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.

von 1,9 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community