556 views
2 votes
2 votes

Which of the following is/are undecidable?

  1.  A = { M| M is TM that accepts exactly  all the odd length strings}
  2.  L = { M|M is a TM and L(M) is infinite}
  3.  EQ = {<D,E> | D is a DFA , E is a regular expression and L(D) = L(E) }

Here is my doubt:

option a: we can construct a TM which goes to final state for odd lengths and for even goes to non-final , since TM we are able to create for it hence DECIDABLE

option b: Languages accepted by TM are also called Turing recognizable i.e nothing but recursively enumerable languages and these languages are undecidable for infinite problem hence , UNDECIDABLE

option c: straight forward it’s decidable

 

According the key option ‘a’ is also UNDECIDABLE why is that, where am I going wrong and is the idea I’ve thought for option ‘b’ correct?

3 Answers

0 votes
0 votes

For option a. it could be possible, let’s assume a TM that has two states, such that at state q0 it accepts all the odd strings and at q1 it accepts the even strings. But might be possible that the at state q0, it loops, forever and never gives any results. Hence we can say that it is undecidable. 

0 votes
0 votes

According to me, the answer should be decidable , undecidable  and undecidable. Reason for option “c” being undecidable, because there can be any random DFA and the regular expression   can be any random expression. It is or isn’t possible for the regular expression to belong to that DFA.

0 votes
0 votes
Option a is undecidable

It is not trivial property of a RE language.

This can be interpreted as

{<M> is TM L(M) is all set of odd length string }

now it is not trivial as it is non trivial property and by rice theorem it is undecidable.

option B is also undecidable and  non recognizable as well.

we can easily proof this using rice theorem taking a counter example of

empty language which is RE and dont have the property that language is infinite so that is non trivial property .so option B is also undecidable.

option C is decidable as we can convert the regular expression to DFA and then then check the languages of both the dfa same or not as it is decidable.

Related questions

0 votes
0 votes
1 answer
1
iam.sahilpatra asked Sep 16, 2023
200 views
Solve this using Adrens lemma rule.
1 votes
1 votes
1 answer
2