search
Log In
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.

in Theory of Computation 227 views
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

1 Answer

0 votes
consecutive a is the acceptance condition

Related questions

2 votes
1 answer
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$ _____________
asked Apr 30, 2019 in Theory of Computation srestha 264 views
0 votes
2 answers
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?
asked Apr 13, 2019 in Theory of Computation srestha 643 views
3 votes
1 answer
3
0 votes
1 answer
4
581 views
TM 'M1' accepts atmost 2 distinct input . TM 'M2' accept more than 2 distinct input . Which of the machine is Turning recognizable ?
asked Dec 1, 2016 in Theory of Computation Neal Caffery 581 views
...