The Gateway to Computer Science Excellence
0 votes

Consider the given below Turing Machine and identify the correct language accepted:

  1. (a+b)*aa(a+b)*
  2. b*a(bb*a)*a
  3. b*ab*a
  4. None of these

The answer is given as (1). But I think (3) is correct as well. Can anyone tell me why only (1) is correct.

in Theory of Computation by (37 points) | 95 views
"aba" belongs to language represented by reg ex 3.

Is it accepted by the turing machine?
the language is set of all strings having two consecutive a's. so option a is correct .

for option c you can clearly se it has strings like "baba" which isn't accepted by the turing machine
aba will reach to q2 not q3
Option 2 cannot accept b*a(bbb......a)

Similarly Option 3 cannot accept abaa

But option 1 is generating abaaab which cannot be accepted.

So option D is correct i think

1 Answer

0 votes
consecutive a is the acceptance condition
by (257 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,615 answers
102,332 users