3.8 Chapter 4

Complete the following problems:

1. (0.25) Do problem 4.4 from the textbook (pg 211). This is the one about a CFG that generates ϵ.

2. (0.25) Do problem 4.8 from the textbook (pg 211). This is the one about the three dimensional countable set.

3. (0.10) Consider the regular expression B = ((c*a) ∪ b)+ for the alphabet Σ = {a,b,c}.

   1. Is <B, cc> ∈ A_{REX}? Explain.

   2. Is <B, bbcab> ∈ A_{REX}? Explain.

4. (0.25) Let ALL_{NFA} = {<A> | A is an NFA and L(A) = Σ*}. Prove the ALL_{NFA} is Turing-decidable.

5. (0.15) Answer TRUE or FALSE for the following statement, and explain your reason: Let L1 be a language such that complement(L1) ∋ Σ1 (not in). Then it is possible that L1 ∈ Σ0.