Assignment 9

Automaton_Theory

陆一洲 5140309557

Problem 1

$$\begin{equation} L_1=\{a^{a_1}b^{b_1}c^{c_1}d^{d_1}e^{c_1}f^{b_1}g^{a_1}h^{e_1}\mid a_1,b_1,c_1,d_1,e_1>0\}\notag\\ L_2=\{a^{a_2}b^{b_2}c^{c_2}d^{d_2}e^{e_2}f^{d_2}g^{c_2}h^{b_2}\mid a_2,b_2,c_2,d_2,e_2>0\}\notag\\ L=L_1\cap L_2\notag \end{equation}$$

Problem 2

Obviously, we have that the class of recursive sets is contained in the class of r.e. sets. What we have to do is to find a set that is in the class of r.e. sets but outside the class of recursive sets.
Here we find $\bar{L}_d=\{x_i\mid x_i\in L(M)\}$. Obviously, $L_d$ is not in the r.e. sets, not to mention recursive sets. For complement is closed ubder recursive sets, $\bar{L}_d$ is not in the recursive sets. And it is also clear that $\bar{L}_d$ is r.e. Thus $\bar{L}_d$ is the set we are determined to find.

Problem 3

If there exists a TM $M_S$ accept a finite set $S$, then we can construct a new TM $M'$. If input $w$, we let $M'$ simulate $M$ on $w$. If $M$ accepts $w$, then $M'$ simulates $M_S$ and accept $x$ according to whether M_s accepts $x$.
Then we can determine that $M$ accepts $w$ if and only if $M'$ accepts $S$, where we can reduce the problem to whether $M$ accepts $w$.
However, whether $M$ accpets $w$ is nondeterministic. Therefore, it is nondecidable that $M'$ can accept $S$.