Consider the following languages.

• ANFAFIN = {hNi | N is an NFA and L(N) is finite}

• EREX = {hRi | R is a regular expression and L(R) = ∅}

• EQREX = {hR1, R2i | R1 and R2 are regular expressions and L(R1) = L(R2)}

• EQNFAFINSET = {hN, Ui | N is an NFA, U is a finite set of words, and L(N) = U}

• ALLREX = {hRi | R is a regular expression and L(R) = {0, 1} ∗}

Answer the following questions based on the NFA N as shown below. Simply say yes or no.

1. Is hNi ∈ ANFAFIN?

2. Is h(0|1)∗ i ∈ EREX?

3. Is h00∗ , 0 ∗0i ∈ EQREX?

4. Is hN, {0, 01, 0110}i ∈ EQNFAFINSET?

5. Is h((0|1)∗ (0|1)∗ )|0i ∈ ALLREX?

6. Is ANFAFIN decidable? If yes, please give a Turing machine which decides ANFAFIN (a highlevel description with stages is enough); otherwise, please prove it, say, by contradiction

7. Is EQNFAFINSET decidable? If yes, please give a Turing machine which decides EQNFAFINSET (a high-level description with stages is enough); otherwise, please prove it, say, by contradiction.

 

Ib 0 S