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:

- aa*b
- abab
- aba*b
- aba*

+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.

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,597 answers

195,837 comments

102,139 users