Vorlesung 4 Merkelt

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Folie 11 2 Folie 26 3 Folie 28 4 Folie 29 5 Folie 32 6 Folie 33

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