509 views
1 votes
1 votes

consider a language which contains encodings of all DFA’s together with strings that the DFA’s accept.
LDFA={ 〈B,w〉 | B is a DFA that accepts input string w}
Assume LDFA ≤m Lx, i.e. Problem LDFA is polynomial time reducible to problem Lx.
 

  1.    Lx must be regular
  2.    Lx must be undecidable
  3.    Lmust be decidable

Please log in or register to answer this question.

Related questions

1 votes
1 votes
1 answer
3
Abhipsa asked Jan 22, 2019
345 views
What is the difference between Turing Recognizable and Turing Decidable?Thanks!
0 votes
0 votes
0 answers
4
Abhipsa asked Jan 22, 2019
255 views
What does this statement mean?There exists a Turing Machine that enumerates a set S of (encoding of) decider Turing Machines such that S includes Turing Machines that dec...