UGC NET CSE | June 2016 | Part 3 | Question: 57

Question

Given a Turing Machine

$M=(\{q_0, q_1, q_2, q_3\}, \{a,b\}, \{a, b, B\}, \delta, B, \{q_3\})$

where $\delta$ is a atransaction function defined as

$\delta(q_0,a)=(q_1, a, R)$

$\delta(q_1, b)=(q_2, b, R)$

$\delta(q_2, a)=(q_2, a, R)$

$\delta(q_2,b)=(q_3, b, R)$

The language L(M) accepted by the Turing machine is given as:

• A. aa*b
• B. abab
• C. aba*b
• D. aba*

Answer 1

Turing machine head movement only right direction...

We can build dfa for it..

Total 4 states are given ...

(q0,a) gives q1 no transition for b

(q1,b) gives q2 no transition for a

That means string start with ab

Now ..(q2,a) gives q2 that means it is loop on q2...

From (q2,b) go to q3 and after that no transition... That means string end with" b"

So C. Is right ans.

Answer 2

C is Ans.

Whenever all the states in TM are  Right Or Left @ time it works like DFA.

So here it is DFA like below fig.

Answer 3

According to given question, we have transtion:
δ(q₀, a) = (q₁, a, R)
δ(q₁, b) = (q₂, b, R)
δ(q₂, a) = (q₂, a, R)
δ(q₃, b) = (q₃, b, R)
We can draw a DFA:

Language will be aba*b.
So, option (C) is correct.