91Ó°ÊÓ

Examine the following formal descriptions of sets so that you understand which members they contain. Write a short informal English description of each set.

1. $\{\mathbf{1}\mathbf{,}\mathbf{3}\mathbf{,}\mathbf{5}\mathbf{,}\mathbf{7}\mathbf{,}...\}$
   
2. $\{...\mathbf{,}\mathbf{-}\mathbf{4}\mathbf{,}\mathbf{-}\mathbf{2}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{4}\mathbf{,}...\}$
   
3. $\mathbf{\{}\mathbf{n}|\mathbf{n}\mathbf{=}\mathbf{2}\mathbf{m}$for someminN}
4. $\mathbf{\{}\mathbf{n}|\mathbf{n}\mathbf{=}\mathbf{2}\mathbf{m}$for someminN, and$\mathbf{n}\mathbf{=}\mathbf{3}\mathbf{k}$for somekinN}
5. $\mathbf{\{}\mathbf{w}|\mathbf{w}$is a string of$\mathbf{0}\mathbf{s}$and$\mathbf{1}\mathbf{s}$andwequals the reverse ofw}
6. $\mathbf{\{}\mathbf{n}|\mathbf{n}$is an integer and$\mathbf{n}\mathbf{=}\mathbf{n}\mathbf{+}\mathbf{1}\mathbf{\}}$

Question: Answer all parts for the following DFA and give reasons for your answers.

$$\begin{gathered} \mathbf{\text{a.Is}}<M,0100>\mathbf{∈}{\mathit{A}}_{\mathbf{D}\mathbf{F}\mathbf{A}}\mathbf{}\mathbf{}\mathbf{?}\mathbf{} \\ \mathit{b}\mathbf{.}\mathbf{}\mathit{I}\mathit{s}\mathbf{}\mathbf{}<M,011>\mathbf{∈}{\mathit{A}}_{\mathbf{D}\mathbf{F}\mathbf{A}}\mathbf{?}\mathbf{} \\ \mathit{c}\mathbf{.}\mathbf{}\mathit{I}\mathit{s}\mathbf{}<M>\mathbf{∈}{\mathit{A}}_{\mathbf{D}\mathbf{F}\mathbf{A}}\mathbf{}\mathbf{?}\mathbf{} \\ \mathit{d}\mathbf{.}\mathbf{}\mathit{I}\mathit{s}\mathbf{}<M,0100>\mathbf{∈}{\mathit{A}}_{\mathbf{R}\mathbf{E}\mathbf{X}}\mathbf{}\mathbf{?}\mathbf{} \\ \mathit{e}\mathbf{.}\mathbf{}\mathit{I}\mathit{s}<M>\mathbf{∈}{\mathit{E}}_{\mathbf{D}\mathbf{F}\mathbf{A}}\mathbf{}\mathbf{}\mathbf{?}\mathbf{} \\ \mathit{f}\mathbf{.}\mathbf{}\mathit{I}\mathit{s}\mathbf{}<M,M>\mathbf{∈}\mathit{E}{\mathit{Q}}_{\mathbf{D}\mathbf{F}\mathbf{A}}\mathbf{}\mathbf{}\mathbf{?} \end{gathered}$$

Question: Answer each part TRUE or FALSE.

$$\begin{gathered} \mathit{a}\mathbf{.}\mathbf{2}\mathit{n}\mathbf{=}\mathit{O}\left(n\right) \\ \mathit{b}\mathbf{.}{\mathit{n}}^{\mathbf{2}}\mathbf{=}\mathit{O}\left(n\right)\mathbf{·}\mathit{A} \\ \mathit{c}\mathbf{.}{\mathit{n}}^{\mathbf{2}}\mathbf{=}\mathit{O}\left(nlog2n\right)\mathbf{·}\mathit{A} \\ \mathit{d}\mathbf{.}\mathit{n}\mathit{l}\mathit{o}\mathit{g}\mathit{n}\mathbf{=}\mathit{O}\left(n^2\right) \\ \mathit{e}\mathbf{.}\mathbf{3}\mathit{n}\mathbf{=}\mathbf{2}\mathit{O}\left(n\right) \\ \mathit{f}\mathbf{.}{\mathbf{2}}^{\mathbf{2}\mathbf{n}}\mathbf{=}\mathit{O}\left(2^{2n}\right) \end{gathered}$$

For each of the following languages, give two strings that are members and two strings that are not members—a total of four strings for each part. Assume the $\mathrm{Î\pounds }=\left\{\mathrm{a},\mathrm{b}\right\}$alpha-alphabet in all parts.

$$\begin{gathered} a.a*b* \\ b.a\left(ba\right)*b \\ c.a*∪b* \\ d.\left(aaa\right)* \\ e.\mathrm{Î\pounds }*a\mathrm{Î\pounds }*b\mathrm{Î\pounds }*a\mathrm{Î\pounds }* \\ f.aba∪bab \\ g.(\mathrm{Î\mu }∪a)b \\ h.(a∪ba∪bb)\mathrm{Î\pounds }* \end{gathered}$$

Let

$A/B=\left\{w\right|wx∈aAforsomex∈B\}$Show that if$A$is context free and$B$is regular, then$A/B$is context free

In certain programming languages, comments appear between delimiters such as #and $\#/$. Let Cbe the language of all valid delimited comment strings. A member of Cmust begin with $\#/$and end with $\#/$but have no intervening $\#/$. For simplicity, assume that the alphabet for Cis $∑=\{a,b,/,\#\}$.

a. Give aDFA that recognizes C.

Show that A is decidable iff $A{≤}_m{0}^{*}1*$.

Show that the function K(x) is not a computable function.

Let $\mathbf{CNFk}=\left\{\right\}$ is a satisfiable cnf-formula where each variable appears in at most k places}.

a. Show that$\mathbf{CNF}\mathbf{2}?\mathbf{P}$ .

b. Show that$\mathbf{CNF}\mathbf{3} \mathbf{is}\mathbf{NP}$-complete.