The Gateway to Computer Science Excellence
+1 vote

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:

  1. aa*b
  2. abab
  3. aba*b
  4. aba*
in Theory of Computation by Veteran (105k points)
recategorized by | 1.3k views

3 Answers

+5 votes
Best answer
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.
by Boss (25.5k points)
selected by
+2 votes

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.

by Boss (23.8k points)
edited by
0 votes

According to given question, we have transtion:
δ(q0, a) = (q1, a, R)
δ(q1, b) = (q2, b, R)
δ(q2, a) = (q2, a, R)
δ(q3, b) = (q3, b, R)
We can draw a DFA:
Language will be aba*b.
So, option (C) is correct.

by Active (1.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,597 answers
102,139 users