1. Convert the following CFG to a PDA using the construction given in class S ! aAbS j bBaS j ? A ! aAbA j ? B ! bBaB j ? 2. Convert the following PDA to a CFG using the construction given in class start q0 q1 q2 q3 ?; ? ! $ 0; ? ! 0 1; 0 ! ? 1; 0 ! ? ?; $ ! ? 3. A TM with stay put instead of left is similar to an ordinary TM, but the transition function has the form δ : Q × Γ ! Q × Γ × fR; Sg At each step, the machine can move to the right or stay on the currently scanned square. Show that this TM model is not equivalent to the standard model. What class of languages does this model recognize? 4. For each of the following operations, give a high-level explanation of why the decidable languages are closed under the operation (a) Concatenation (b) Intersection (c) Complement 5. Give a high level description of an algorithm to show that Lnb = fhMi j M when started on the blank tape, eventually writes a nonblank symbolg is decidable. (HINT: If M has m states, how many moves will it take before you can tell?) 6. Let u; v be strings. We will write u ≺ v if u (strictly) precedes v in the standard string ordering: ? ≺ 0 ≺ 1 ≺ 00 ≺ 01 : : : . An enumerator E respects ≺ if for any strings u and v that it enumerates, if it outputs u before it outputs v then it must be the case that u ≺ v. Prove the following: a language L is Turing-decidable if and only if it is enumerated by an enumerator that respects ≺. 1
