1b. The problem of determining whether a DFA accepts at least one string. Note that we do not care which string it accepts as long as it accepts at least one string.

1c. The problem of determining whether a DFA accepts the empty string. In other words, the language of a DFA is ? ? L for a language L.

1d. The problem of determining whether the language of an NFA is not empty

1e. The problem of determining whether a regular expression does not generate a specific string )

1i. The problem of determining whether two deciders produce the same output on their tape (after they halt in their accept state) for a given input string. Note that a decider is a Turing machine that always halt.

Show that the following languages are decidable. Note that you are allowed to use the following deciders (Turing machines) as a subroutine: 1 TM M that decides ADFA from Theorem 4.1

2 TM N that decides ANFA from Theorem 4.2

3 TM P that decides AREX from Theorem 4.3

4 TM T that decides EDFA from Theorem 4.4

5 TM F that decides EQDFA from Theorem 4.5

Also assume that a Turing machine can construct DFA based on closures of regular languages and perform conversions among DFA, NFA, and regular expression. Note that for each of your Turing machine, you MUST explain why it demonstrates that the language is decidable (your machine is always halt and your machine is a decider for the language).

(a) Show that the language from the question 1(b) is decidable.

(b) Show that the language from the question 1(c) is decidable.

(c) Show that the language from the question 1(d) is decidable.

(d) Show that the language from the question 1(e) is decidable. For this question, simply construct a Turing machine. You do not have to show that your machine is a decider for the language.

(e) Show that the language from the question 1(i) is decidable. For this question, simply construct a Turing machine. You do not have to show that your machine is a decider for the language.