This flashcard is just one of a free flashcard set. See all flashcards!

zwei TMn, die bzw. entscheiden (erkennen).

Konstruieren eine TM M, die entscheidet (erkennt)

- simuliere das Verhalten von auf w, dann das Verhalten von auf w
- Falls und akzeptieren, so auch M

=> M akzeptiert offensichtlich die Eingaben von , da sowohl als auch auf jeder Eingabe halten. Also entscheidet (erkennt) M die Sprache .