Turing decidable/undecidable

110 Views Asked by At

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

can you prove whether $X$ is Turing decidable/undecidable?

this question could be on my exam this week and I need to understand it. please help.

2

There are 2 best solutions below

3
On

Per Rice's Theorem, since accepting the empty language is a nontrivial property, $X$ is undecidable. See also this CS link.

0
On

This is decidable. A description of a DFA is a directed graph with labelled edges, and to determine if the language accepted by the DFA is nonempty one need only determine if there is any path from the start state, following these directed edges, to some accepting state. Pick your favorite graph search algorithm to do this.