Question 1. (10+20 marks) For a finite automata F = (Q, q0, Σ, δ, F ) and input x, define a configuration of F to be the pair q, y where q ∈ Q, y is a suffix of x, and automata F on input x = zy, ends up in state q after reading z. Note that if F is an NFA, then there may be more than one state in which F ends in after reading z. An accepting configuration sequence is a string q0, y0 q1, y1 · · · qm, where (1) each qi, yi is a configuration, (2) F moves from configuration qi, yi to qi+1, yi+1 in one step, (3) qm ∈ F , and (4) y0 = x.
Prove that
• Input x is accepted by F iff there exists an accepting configuration sequence that starts with q0, x .
• The set of all accepting configuration sequences of F is computable but is not a CFL.
Question 2. (20 marks) A 2-PDA is a pushdown automata with two stacks. In a transition, the automata can push/pop both stacks independently. Prove that any computable set can be accepted by a 2-PDA.
Question 3. (20 marks) A counter TM is a Turing machine with an input tape that is read-only (input is initially written on the tape and cannot be changed during computation) and a finite number of counters. In one move of the TM, a counter either remains unchanged, or is incremented by one, or is decremented by one. Prove that every computable set can be accepted by a counter TM.
Question 4. (20 marks) Design a Turing Machine (draw the state diagram) to multiply two numbers represented in unary alphabet, that is, 1 is represented as 1, 2 as 11, 3 as 111,
• . .. The input alphabet is Σ = {1, ×, =}. Input has the form 1n × 1m =, which denotes multiplication of number n with m. The TM should write the result of the multiplication, 1nm, as output immediately after the = sign on the tape.
Question 5. (20 marks) Design a TM (draw the state diagram) that accepts following set of strings:
L = {ww | w ∈ {a, b}∗}.
Question 6. (10 marks) Prove that the following set is not computable:
L = {(p, q) | there exists a string x accepted by both TM Mp and TM Mq}.
1
