Chapter 10: Decidability and Recursively Enumerable Languages Q 319
SELF-TEST
1. What is the difference between a recursive language and a recursively
enumerable language?
2. The DFA M is given by
M = ({Cia, % Q2, Ci3}, to, 1}, 0, qo, {Qo})
where {) is defined by the transition Table 10.1.
TABLE 10.1 Transition Table for Self-Test 2
State
0
-,>@
q2
q1
q1
q3
qo
q2
qo
q3
q3
q1
q2
Answer the following:
(a) Is (A1, 001101) in A uA ?
(b) Is (M, 01010101) in A DL ;.?
(c) Does M E A DFA ?
(d) Find w such that (lvI, w) E A DFA .
3. What do you mean by saying that the halting problem of TM is
undecidable?
4. Describe A DFA , A CFG , A csG , A TM , and HALT Tlv1 '
5. Give one language from each of ;i rl, ;i ell, ot c,I'
6. Give a language
(a) which is in ;f csl but not in ;r: rl
(b) which is in ;f ell but not in J: c51
(c) which is in ;i ell but not in ;irl'
EXERCISES
10.1 Describe the Euclid's algorithm for finding the greatest common
divisor of two natural numbers.
10.2 Show that A NDFA = {(B, w) I B is an N DFA and B accepts w} IS
decidable.
10.3 Show that E DFA = {M I M is a D FA and T(M) = 0} is decidable.
10.4 Show that EQDFA = {(A, B) IA and Bare DFAs and T(A) = T(B)} IS
decidable
10.5 Show that E CFG is decidable (E CFG is defined in a way similar to that
of E DFA ).