91Ó°ÊÓ

$\mathbf{Let}{\mathbf{BAL}}_{\mathrm{DFA}}=\left\{\left(\mathbf{M}\right)\right|\mathbf{M}$is a DFA that accepts some string containing an equal number of 0s and 1s}. Show that ${\mathbf{BAL}}_{\mathrm{DFA}}$ is decidable.

Let $\mathbf{C}\mathbf{=}\mathbf{\left\{}\mathbf{\right\{}\mathbf{G}\mathbf{,}\mathbf{x}\mathbf{\left\}}\mathbf{\right|}\mathbf{G}\mathbf{}\mathbf{is}\mathbf{}\mathbf{a}\mathbf{}\mathbf{CFG}\mathbf{}\mathbf{x}\mathbf{}\mathbf{is}\mathbf{}\mathbf{a}\mathbf{}\mathbf{substring}\mathbf{}\mathbf{of}\mathbf{}\mathbf{some}\mathbf{}\mathbf{y}\mathbf{∈}\mathbf{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}\mathbf{\}}\mathbf{.}$ Show that$\mathbf{C}$ is decidable.

The proof of Lemma 2.41 says that $\mathbf{(}\mathbf{q}\mathbf{,}\mathbf{x}\mathbf{)}$ is a looping situation for a DPDA$\mathbf{P}$ if when$\mathbf{P}$ is started in state q with$\mathbf{x}\mathbf{∈}\mathbf{Γ}$ on the top of the stack, it never pops anything below$\mathbf{x}$ and it never reads an input symbol. Show that$\mathbf{F}$ is decidable, where$\mathbf{F}\mathbf{=}\mathbf{\left\{}\mathbf{(}\mathbf{P}\mathbf{,}\mathbf{q}\mathbf{,}\mathbf{x}\mathbf{)}\mathbf{|}\mathbf{(}\mathbf{q}\mathbf{,}\mathbf{x}\mathbf{)}\mathbf{is}\mathbf{a}\mathbf{looping}\mathbf{situation}\mathbf{for}\mathbf{P}\mathbf{\right\}}\mathbf{.}$

Let . Show that$\mathit{A}\mathit{L}{\mathit{L}}_{\mathbf{\text{DFA}}}$is decidable.

Let . Show that$\mathit{A}{\mathit{Î\mu }}_{\mathbf{\text{CFG}}}$is decidable.

Let .Show that $\stackrel{\mathbf{¯}}{{\mathbf{E}}_{\mathbf{\text{TM}}}}$, the complement of ${\mathit{E}}_{\mathbf{\text{TM}}}$, is Turing-recognizable.

Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. We describe the functions

Answer each part and give a reason for each negative answer.

a. Is f one-to-one?

b. Is f onto?

c. Is f a correspondence?

d. Is g one-to-one?

e. Is g onto?

f. Is g a correspondence?