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.
- Lx must be regular
- Lx must be undecidable
- Lx must be decidable