Computability - Models of Computation: Exploring the Power of Computing - page 224

THEOREM 5.7.1 The language L RX is decidable.
Proof To decide on a string R , w , use the method of Theorem 4.4.1 to construct a NFSM
M 1 that accepts the language described by R . Then invoke the method of Theorem 4.2.1
to construct a DFSM M 2 accepting the same language as M 1 .Thestring w is given to M 2 ,
which accepts it if R can generate it and rejects it otherwise. This procedure decides

L RX

because it halts on all strings R , w ,whetherin

L RX or not.

As a second example, we show that finite-state machines that recognize empty languages
are decidable. Here an FSM encoded as Turing machine reads one input from the tape per
step and makes a state transition, halting when it reaches the blank letter.

THEOREM 5.7.2 The language L = {ρ ( M ) | M is a DFSM and L ( M )= ∅} is decidable.
Proof L ( M ) is not empty if there is some string w it can accept. To determine if there
is such a string, we use a TM M that executes a breadth-first search on the graph of the
DFSM M that is provided as input to M . M first marks the initial state of M and then
repeatedly marks any state that has not been marked previously and can be reached from a
marked state until no additional states can be marked. This process terminates because M
has a finite number of states. Finally, M checks to see if there is a marked accepting state
that can be reached from the initial state, rejecting the input ρ ( M ) if so and accepting it if
not.

The third language describes context-free grammars generating languages that are empty.
Here we encode the definition of a context-free grammar G as a string ρ ( G ) over a small
alphabet.

THEOREM 5.7.3 The language L = {ρ ( G ) | G is a CFG and L ( G )= ∅} is decidable.
Proof We de s i gn a TM M that, when given as input a description ρ ( G ) of a CFG G ,
first marks all the terminals of the grammar and then scans all the rules of the grammar,
marking non-terminal symbols that can be replaced by some marked symbols. (If there is a
non-terminal A that it is not marked and there is a rule A BCD in which B , C , D have

already been marked, then the TM also marks A .) We repeat this procedure until no new
non-terminals can be marked. This process terminates because the grammar G has a finite
number of non-terminals. If S is not marked, we accept ρ ( G ) . Otherwise, we reject ρ ( G )
because it is possible to generate a string of terminals from S .

→

5.7.2 A Language That Is Not Recursively Enumerable
Not unexpectedly, there are well-defined languages that are not recursively enumerable, as we
show in this section. We also show that the complement of a decidable language is decidable.
This allows us to exhibit a language that is recursively enumerable but undecidable.
Consider the language L 1 defined below. It contains the i th binary input string if it is not

accepted by the i th Turing machine.

w i is not accepted by M i }
THEOREM 5.7.4 The language L 1 is not recursively enumerable; that is, no Turing machine exists
that can accept all the strings in this language.

L 1 = { w i |