Assignment 4

Automaton_Theory

陆一洲 5140309557

Problem 1

Let $L$ be a set of strings of $0$'s and $1$'s. Use $h$, $h^{-1}$ and intersection with regular set to delete all even numbered symbols in strings of $L$.

Define

$$\begin{align*} h_1(a)=a, h_1(\hat{a})=a\\ h_2(a)=a, h_1(\hat{a})=\epsilon \end{align*}$$ Then the answer is $$h_2\left(h_1^{-1}(L)\cap L\left(\left((0+1)\left(\hat 0+\hat 1\right)\right)^*(\epsilon+00+1)\right)\right)$$

Problem 2

Define $\mathrm{Half}(L)=\left\{x\mid \exists\ y,|y|=|x|,xy\in L\right\}$. Let $M=\{Q,\Sigma,\delta,q_0,F\}$ be a finite automaton. Construct a finite automaton accepting $\mathrm{Half}(L(M))$.

We can have

$$\mathrm{Half}(L(M))=(Q',\Sigma',\delta',q'_0,F')$$ where
$$\begin{aligned} Q'&=\{f_0\}\cup\left\{[r,s,t]\mid r,s,t\in Q \right\}\\ \Sigma'&=\{0,1\}\\ \delta'([r,s,t],a)&=\left\{[\delta(r,a),\delta(s,b),t]\mid b\in\Sigma\right\}\\ \delta'(f_0,\epsilon)&=\left\{[q_0,t,t]\mid t\in Q\right\}\\ q'_0&=f_0\\ F'&=\left\{[r,s,t]\mid r=t,s\in F \right\} \end{aligned}$$

Problem 3

Use the pumping lemma to prove that $\{a^ib^j\mid i\textrm{ and }j\textrm{ are relatively prime}\}$ is not a regular set.

We can simply pick out a $w$ with length $l\geqslant n$ at the bound of $a$'s and $b$'s, and take

$$\begin{aligned} x&=a^p\ \ \ (\ p+2\leqslant n\ )\\ y&=ab\\ z&=b^q\ \ \ (\ p+q+2=l\ ) \end{aligned}$$ Obviously, it satisfies that $y\neq\epsilon$ and $|xy|\leqslant n$, but it does not satisfy that $\forall\ k\geqslant 0,\ xy^kz\in L$.
Thus, $\{a^ib^j\mid i\textrm{ and }j\textrm{ are relatively prime}\}$ is not a regular set.