You only need to construct a TM that decides on a ...null language!
So, regardless of input X, the DFA B for the complementary input, will obey L(compliment of X)=...
Givenand <A> is some encoding of machine ACode:M = {<A> | A is DFA and L(A) = empty set }
Is M decidable?
Can someone work with me on how to solve these kinds of problems. This is example problem. We can walk trought similar problems. All online examples seems to be too abstract.
help would be much appreciated
thank you
hi
thanks for response
how do you answer these questions in general.
i know DFA for empty is just machine with one state which is final as well
i am just confused how to build these TM . How do you use universal machine in these kinds of questions?
Many questions about DFAa are decidable because finite automata have finitely many instructions and finite memory, so they can be exhaustively explored. For example, to check if an automaton does not accept any words, one needs to follow all possible paths starting from the initial state and make sure that one cannot arrive at the accepting state. So this is a graph reachability problem.
To understand these things, the best thing is to read a good textbook, such as Elements of the Theory of Computation by Lewis and Papadimitriou. Feel free to post other questions here as well.