Vorlesung 4 Merkelt
Aus ProgrammingWiki
Archivierte Version vom 2021-04-19T09:07:30+00:00. Aktuelle Version
Inhaltsverzeichnis |
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 c(w) = \overline{\chi_M(w)} = \begin{cases} False & w \in M\\ True & w \in A^\ast \backslash M \end{cases}