Vorlesung 4 Merkelt

Folie 11

Folie 26

Folie 28

M entscheidbar \Longrightarrow M, A^\ast \backslash M aufzählbar

M entscheidbar \Longrightarrow M aufzählbar \checkmark (siehe Satz 3)

Zu zeigen: M entscheidbar \Longrightarrow A^\ast \backslash M aufzählbar

\chi_M(w) = \begin{cases} True & w \in M\\ False & w \in A^\ast \backslash M \end{cases} lt. Voraussetzung

Sei \chi_{A^\ast \backslash M}(w) = \overline{\chi_M(w)} = \begin{cases} False & w \in M\\ True & w \in A^\ast \backslash M \end{cases}

Folie 29

Folie 32

Folie 33