Lecture: TM

$1.$ For the following Turing machine M $=($Q$,\backslash$Sigma $,\backslash$Gamma $,\backslash$delta $,$ q$1,$ qaccept, qreject$)$ with

Q $=\{$q$1,...,$ q$8,$ qaccept, qreject$\},$

$\backslash$Sigma $=\{0,1,$ #$\},$

$\backslash$Gamma $=\{0,1,$ #$,$ x$,\},$

and transitions below. $(20$ points$)$

The reject state and the transition to qreject is not highlighted in the above figure. If there is no outgoing transition for a given state, it goes to qreject and the head does not change the tape and just moves right.

Please show the sequence of configurations when the Turing machine input tape is string $1$#$1.$

Answer:

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.