Undecidability

Let’s start the day with a table of decidability construction:

Language	Setbuilder	Proof Idea
$A_{D F A}$	${⟨ M, w ⟩ ∣ M is a DFA and w is a string and m accepts w}$	Simulated DFA on input w
$A_{NF A}$	${⟨ N, w ⟩ ∣ N is an NFA and N accepts w}$	Convert $N$ to an equivalent DFA by subset construction, use decider for $A_{D F A}$
$A_{REGEX}$	${⟨ R, w ⟩ ∣ R is a REGEX and R matches w}$	convert $R$ to an equivalent NFA by prior Theorem, use $A_{NF A}$
$E_{D F A}$	${⟨ D ⟩ ∣ D is a DFA and L (D) = \emptyset}$	graph search to find path between start and accept states
$E Q_{D F A}$	${⟨ D_{1}, D_{2} ⟩ ∣ D_{1}, D_{2} DFAs and L (D_{1}) = L (D_{2})}$	$D_{3 ∣ L}$