Problem 1 The terms "decidable" and "recognizable" refer to languages, not strings. Let L = {0,1}. Part (a) Show that for every string w E L', there is a Turing-decidable language Lcontaining w. Part (b) Show that for every string w L*, there is a Turing-recognizable language L2 that contains w and is not Turing-decidable. Problem 2 Consider the following language: WAYPOINT NFA = {(M,9,r)|M = (Q,8,8,90,F) is an NFA, q, r e Q, and there is a string w e L(M) such that M accepts w on a path that goes through q then r}. If q = r, then "goes through q then r" just means "goes through q = r." Show that WAYPOINT NFA is Turing-decidable. Problem 3 Consider the following language: WAYPOINT PDA = {(M,9,r)|M is a PDA, 9.r are states in M, and there is a string w E L(M) such that M accepts w on a path that goes through q then r}. If q = r, then goes through then r" just means "goes through q = r." Show that WAYPOINT PDA is Turing-recognizable