retagged by
425 views
0 votes
0 votes

Which of the following statements is correct about the given Turing Machine transitions below?

$\begin{array}{|c|c|c|c|} \hline \delta & 0 & 1 & B \\ \hline q0 & (q1,1,R) & (q1, 1,R) & \text{Halt} \\ \hline q1 & (q0, 0, R) & (q0, 1, R) & (qf, B, R) \\ \hline qf & \text{Halt} & \text{Halt} & \text{Halt} \\ \hline \end{array}$

Where, 
$\lceil = \{0,1,B\}$
$Q = \{q0 ,q1 ,qf \}$ 
Final State, $F = \{qf \}$
Initial State $= q0 $

  1. TM does not halt on any string start with $‘1'$.
  2. TM halts on all strings of odd length and accepts it.
  3. TM does not halt on all strings in $\Sigma ^*$.
  4. TM halts on all strings of even length. 
  1. I and II
  2. II and IV
  3. II and III
  4. I , II and III
retagged by

1 Answer

Best answer
4 votes
4 votes

The State Diagram of the given TM is 

Clearly, all the strings of even length halt at q0 (Non-final state).

All the strings of odd length halt at qf. qf is the final state means given TM is accepting all the string of odd length.

Ans: Option B , II and IV both are correct statements.
 

selected by
Answer:

Related questions

4 votes
4 votes
0 answers
2
Bikram asked Aug 12, 2017
602 views
The number of possible finite automata with two states $a0$ and $a1$ (where $a0$ is always the initial state over the alphabet $\{p, q\}$) which accepts empty language is...
0 votes
0 votes
1 answer
3
Bikram asked Aug 12, 2017
259 views
What is the regular expression corresponding to the above DFA?$(01 + (00)^*1)^*$$0^*10^*$$(10 + 0(00)^* (1 + 01) )^*$$0(00)^*10^*$