HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Decide whether a DFA accepts the empty language

Submitted by: @import:stackexchange-cs··
0
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?

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):

  • 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.