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 = {(R₁, R₂) | R₁ and R₂ are regular expressions and L(R₁) ⊆ L(R₂)}.(Hint: Note that L(R₁) ⊆ L(R₂) if and only if L(R₁) ∩ L(R₂) = Φ.)

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:

CFL_TM = {(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:

A₀₁ = {(M) | M is a TM and 01 ∈ L(M ) (i.e., M accepts string 01)}. (Hint: Show that ATM can be reduced to A₀₁.)

Question 6. We mentioned in class that the following language is undecidable:
ALL_CFG = {(G) | G is a CFG and L(G) = Σ*, where Σ is set of all terminals of G}.

Prove the following language is undecidable by reducing ALL_CFG to it:

EQ_CFG = {(G₁, G₂) | G₁ and G₂ are CFGs and L(G₁) = L(G₂)}.

Question 7. Prove the following language A_HALT is Turing-recognizable:

A_HALT = {(M) | M is a TM and M halts on some input}.