# TOC-Turing Machine

1 vote
227 views

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.

0
"aba" belongs to language represented by reg ex 3.

Is it accepted by the turing machine?
1
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
0
aba will reach to q2 not q3
0
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

consecutive a is the acceptance condition

## Related questions

1
264 views
$P_{1}:$ {$<M>|M$ is a TM that accepts atleast $2$ strings of different length} $P_{2}:$ {$<M>|M$ is a TM and there exists an input whose length less than $100,$ on which $M$ halts } The number of problem which is $RE$ but not $REC$ _____________
2
643 views
Consider $\left \langle M \right \rangle$ be the encoding of a turing machine as a string over alphabet $\Sigma =\left \{ 0,1 \right \}$. Consider $D=${$\left \langle M \right \rangle$ $M$ ... Recursive $(B)$ Non-Recursive $(C)$ Recursively enumerable $(D)$ Not Recursively enumerable My question is Is it not a Halting Problem they are asking for?
3
252 views
When a Multi-tape TM of time complexity T(N) is reduced to a single tape turing machine, the complexity can go upto?