Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

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 .