Lecture: Decidability

$2.$ Let A$\backslash$epsi CFG $=\{$G$|$ G is a CFG that generates $\backslash$epsi $\}.$ Show that A$\backslash$epsi CFG is decidable. $(20$ points$)$

$($Hints: Create a Turing machine M$,$ For each x$$L$,$ M either accepts or rejects x$)$

Answer:

Lecture: Decidability

$3.$ In the chapter of regular language, we know that the DFA is equivalent with NFA and regular expression $($RE$).$ For the problem to determine whether a given DFA and RE are the same, C $=\{|$ D is a DFA and R is a RE that L$($D$)=$ L $($R$)\},$ please prove that C is decidable. $(20$ points$)$

$($Hints: Create a Turing machine M$,$ For each x$$L$,$ M either accepts or rejects x$)$

Answer:

Lecture: Reducibility

$4.$ Show that EQ CFG is undecidable. $(20$ points$)$

Hint: You can directly use the result of Theorem $5\mathrm{.}13.$ That is$,$ instead of considering a reduction from ATM, you can directly consider a reduction from ALLCFG.

Lecture: Complexity

$5.$ Answer each part TRUE or FALSE. $(20$ points$)$

a$.2$n $=$ O$($n$).$

b$.$ n$2=$ O$($n$).$

c$.3$n $=2$O$($n$).$

d$.22$n $=$ O$(22$n $).$

Please also justify each of your true$/$false answers using the Definition $7\mathrm{.}2.$

In more details: what is f$($n$),$ what is g$($n$),$ whether c and n$0$ exist so that when n$>=$n$0$ that inequation is always true.