0 Daumen
449 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.)

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

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community