Reference no: EM133383854
Models of Computation
Assignment - Computability
Question 1. Prove that the following language A is decidable (e.g., give a TM that decides A):
A = {(M) | M is an NFA and L(M ) = B},
where B = {ω | ω ∈ {0, 1}* and ω contains 001 as a substring}. Note that L(M ) denotes the language of M.
(Hint: Observe that B is a regular language. Recall we studied in class that the language EQDFA is decidable.)
Question 2. Prove that the following language A is decidable (e.g., give a TM that decides A): A = {(R1, R2) | R1 and R2 are regular expressions and L(R1) ⊆ L(R2)}.(Hint: Note that L(R1) ⊆ L(R2) if and only if L(R1) ∩ L(R2) = Φ.)
Question 3. Prove that the following language A is decidable (e.g., give a TM that decides A):
A = {(G) | G is a CFG and ε ∈ L(G)}.
Question 4. Prove the following language is undecidable:
CFLTM = {(M) | M is a TM and L(M ) is a context-free language}.
(Hint: We proved in class that the language REGULARTM is undecidable. Follow the similar idea and slightly modify that proof.)
Question 5. Prove the following language is undecidable:
A01 = {(M) | M is a TM and 01 ∈ L(M ) (i.e., M accepts string 01)}. (Hint: Show that ATM can be reduced to A01.)
Question 6. We mentioned in class that the following language is undecidable:
ALLCFG = {(G) | G is a CFG and L(G) = Σ*, where Σ is set of all terminals of G}.
Prove the following language is undecidable by reducing ALLCFG to it:
EQCFG = {(G1, G2) | G1 and G2 are CFGs and L(G1) = L(G2)}.
Question 7. Prove the following language AHALT is Turing-recognizable:
AHALT = {(M) | M is a TM and M halts on some input}.