621 views
0 votes
0 votes

Let A, B, C be recognizable languages over an alphabet Σ, such that A∪B∪C=Σ and A∩B=∅,B∩C=∅,A∩C=∅ then

  1.   Only A is Turing decidable
  2.   Only B is Turing decidable
  3.   Both A and B is Turing decidable
  4.   None of these

-----i think all three can be turing decidable .

1 Answer

Best answer
2 votes
2 votes

Let TM For A is TA  , Let TM For B is TB , Let TM For C is TC.

A is decidable :

Take any word "w" run on TA if it accept than than w $\epsilon$ A .now suppose "w" is not accepted by TA and may runs infinitely without giving any output.So how can we know that word is $\epsilon$ A or not ??

So run TB AND TC for word "w" if word is accepted by TB or TC that means that word is not $\epsilon$ to A as given in question that A , B and C are mutually exclusive to each other.So for Yes case we have TA and for NO cases we have TB and TC. 

Same way B also Decidable.

correct me!

selected by

Related questions

0 votes
0 votes
2 answers
2
0 votes
0 votes
2 answers
4