Jni:

Section:

$2.$ points, $12$ points per item$]$ Let $L$ be the following langunge:

is a DTM$,w$ is a string, $q$ is a state of $M$ and $q$ is encountered at least once during the execution of $M$ on $w$

$($a$)$ Prove that $L$ is recognizable. You only need to describe a Turing machine that recogyizes L$.$ No justification for its correctness is needed.

PROVE THAT L IS NOT DECIDABLE!!!!