patternMinor
Decide whether a DFA accepts the empty language
Viewed 0 times
dfaacceptstheemptylanguagedecidewhether
Problem
Let $X = \{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\}$ where $\langle M \rangle$ is an encoding of the
machine $M$. Is $X$ Turing decidable? Why or why not?
machine $M$. Is $X$ Turing decidable? Why or why not?
Solution
Re-read your textbook chapter on DFAs and NFAs -- you'll find everything you need to know there.
See also the following questions, which both have answers to your question embedded in their answers (make sure to read carefully):
Next time, tell us what you have tried, to solve the exercise on your own.
See also the following questions, which both have answers to your question embedded in their answers (make sure to read carefully):
- Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?
- Undecidable among these for turing machine
Next time, tell us what you have tried, to solve the exercise on your own.
Context
StackExchange Computer Science Q#18616, answer score: 4
Revisions (0)
No revisions yet.