hw1

formal_language_HW1.pdf

1.a

1.b

1.c

1.d

1.e

2.a

$$\begin{array}{rl}{Q}_1& =a{Q}_2\cup b{Q}_1=b^{\ast }a{Q}_2\\ Q_2& =a{Q}_2\cup b{Q}_0=a^{\ast }b{Q}_0\\ & \\ Q_0& =b{Q}_1\cup a{Q}_0\cup ϵ\\ & =a^{\ast }b{Q}_1\cup ϵ\\ & =a^{\ast }b(b^{\ast }a{Q}_2)\cup ϵ\\ & =a^{\ast }b{b}^{\ast }a(a^{\ast }b{Q}_0)\cup ϵ\\ & =a^{\ast }{b}^{+}{a}^{+}b{Q}_0\cup ϵ\\ & =(a^{\ast }{b}^{+}{a}^{+}b{)}^{\ast }\cup ϵ\\ & =(a^{\ast }{b}^{+}{a}^{+}b{)}^{\ast }\end{array}$$

2.b

$$R=((a^{\ast }\cup b)b(bb{)}^{\ast }a{)}^{\ast }$$

3.a

3.b

3.c

3.d

3.e

4.a

$$R=(0^{\ast }{1}^{+}{)}^3{\Sigma }^{\ast }$$

ref

4.b

$$R=(1^{+}01^{+}01^{\ast })\cup (1^{\ast }01^{+}01^{+})\cup (11^{+}01^{\ast }01^{\ast })\cup (1^{\ast }01^{\ast }011^{+})\cup (011^{+}0)$$

4.c

$$R=(1\circ \Sigma {)}^{\ast }$$

5

If $L$ is regular, then $\min (L)$ is also regular because $\min (L)$ is $L$ but remove the final state that be passing though another final state.

for example

$$L=(ab\cup abc\cup abcd\cup ac)$$

$$min(L)=(ab\cup ac)$$

6.a

$$\begin{array}{rl}{L}^{\ast }& =\bigcup _{i\in \mathbb{N}}{L}^i\\ L^{\ast \ast }& =(\bigcup _{i\in \mathbb{N}}{L}^i{)}^{\ast }\\ & =\bigcup _{j\in \mathbb{N}}(\bigcup _{i\in \mathbb{N}}{L}^i{)}^j\\ & =\bigcup _{j\in \mathbb{N}}\bigcup _{i\in \mathbb{N}}{L}^{ij}\\ & =\bigcup _{ij\in \mathbb{N}}{L}^{ij}\\ & =L^{\ast }\end{array}$$

$$\begin{array}{rl}{L}^{\ast }{L}^{\ast }& =(L^{+}\cup ϵ)(L^{+}\cup ϵ)\\ & =L{L}^{+}\cup L^{+}\cup ϵ\\ & =L^{\ast }\end{array}$$

6.b

$$\begin{gathered} A\text{ is a finite language, then it contains a finite number of strings }{a}_0,a_1,\cdots ,a_n \\ \text{The language }\{a_i\}\text{ consisting of a single literal string }{a}_i\text{ is regular } \\ \text{The union of a finite number of regular languages is also regular.} \\ \text{Therefore }A=a_0,a_1,\cdots ,a_n\text{ is regular} \end{gathered}$$

ref

6.c

$$\begin{gathered} A\subseteq B \\ A=\{a^n{b}^n|n\in {\mathbb{N}}_0\} \\ B=\{(a\cup b{)}^n|n\in {\mathbb{N}}_0\} \end{gathered}$$

6.d

$$\begin{gathered} B\subseteq A \\ A=\{a^n{b}^n|n\in {\mathbb{N}}_0\} \\ B=\{w|w=ab\} \end{gathered}$$

6.e

$$L^{(\frac{1}{3})}=\{w|w^3\in L\}$$

$$L^{(\frac{1}{3})}\text{ mean all the solution that in }L\text{ that can divide to 3 exact same part}$$

6.f

$$\begin{gathered} L^{(3)}=\{w^3|w\in L\} \\ \text{If }L=\{a{b}^{\ast },b\} \\ {L}^{(3)}=\{(a{b}^{\ast }{)}^3,bbb\}=\{a{b}^{\ast }a{b}^{\ast }a{b}^{\ast },bbb\} \\ {w}^3=\underset{x}{\underbrace{w}}\underset{y}{\underbrace{w}}\underset{z}{\underbrace{w}} \\ \text{By pumping lemma} \\ |y|\ge 1 \\ |xy|\le p \\ (\forall k\ge 0)(x{y}^{k}z\in L) \\ \text{But }x{y}^{0}z=ww\notin L \\ \text{Therefor this is not regular languages} \end{gathered}$$

ref (Formal definition)

6.g

If $L$ is regular language then it can convert to DFA.

Divide a DFA to $k$ equeal part still are DFA which make it still regular.

6.h

$$\begin{gathered} L^{\frac{1}{\infty }}=L^1\cap L^{\frac{1}{2}}\cdots \cap L^{\frac{1}{\infty }} \\ \text{since }L\text{ is regular so is the }{L}^{\frac{1}{n}} \\ {L}^{\infty }\text{ are regular because it is interest of }{L}^{\frac{1}{n}} \end{gathered}$$

6.i

$$\begin{gathered} \sqrt{L}=\bigcup _{k\le 1}{L}^{\frac{1}{k}} \\ \sqrt{L}\text{ is regular by union closure} \end{gathered}$$

6.j

not regular

7.a

$$L=\{wcw|w\in \{a,b{\}}^{\ast }\}$$

$$\begin{gathered} wcw=(a\cup b{)}^{i}c(a\cup b{)}^i \\ (a\cup b{)}^{i}c(a\cup b{)}^j=\underset{x}{\underbrace{(a\cup b{)}^{p-i}}}\underset{y}{\underbrace{(a\cup b{)}^i}}\underset{z}{\underbrace{c(a\cup b{)}^p}}\text{ and }i>0 \\ \text{By pumping lemma} \\ |y|\ge 1 \\ |xy|\le p \\ (\forall k\ge 0)(x{y}^{k}z\in L) \\ \text{But }x{y}^{0}z=(a\cup b{)}^{p-i}c(a\cup b{)}^p\notin L \\ \text{Therefor this is not regular languages} \end{gathered}$$

7.b

$$L=\{xy|x,y\in \{a,b{\}}^{\ast }\text{ and }|x|=|y|\}$$

$$\begin{gathered} xy=\{a,b{\}}^p\{a,b{\}}^p \\ x\text{ and }y\text{ is regular languages } \\ w\text{ is regular languages by closure of concatenate} \end{gathered}$$

7.c

$$L=\{a^n|n\text{ is a prime number}\}$$

$$\begin{gathered} a^p=\underset{x}{\underbrace{a^{p-j-i}}}\underset{y}{\underbrace{a^i}}\underset{z}{\underbrace{a^j}} \\ |y|\ge 1 \\ |xy|\le p \\ (\forall k\ge 0)(x{y}^{k}z\in L) \\ \text{But }x{y}^{0}z=a^{p-j-i}{a}^j=a^{p-i}\notin L \\ \text{Therefor this is not regular languages} \end{gathered}$$

7.d

$$L=\{a^m{b}^n|gcd(m,n)=17\}$$

$$\begin{gathered} j,k\in \mathbb{N}\text{ and }gcd(j,k)=1 \\ \text{ then }{a}^m{b}^n=a^{17j}{b}^{17k} \\ {a}^m{b}^n=\underset{x}{\underbrace{a^{17j-i}}}\underset{y}{\underbrace{a^i}}\underset{z}{\underbrace{b^{17k}}} \\ |y|\ge 1 \\ |xy|\le p \\ (\forall k\ge 0)(x{y}^{k}z\in L) \\ \text{But }x{y}^{0}z=a^{17j-i}{b}^{17k}\notin L \\ \text{Therefor this is not regular languages} \end{gathered}$$

8.a

$$\begin{gathered} \text{Base case } \\ i=0,Q_r^0=\{q_0\} \\ \text{ This is trivially true since the only path of length 0 is the path that starts and ends at }{q}_0 \\ \text{Inductive Step} \\ \text{Assume that for some }k\ge 0,Q_r^k\text{ is the set of all reachable states from }{q}_0\text{ using paths of length }k. \\ \text{By definition, }{Q}_r^{k+1}\text{ includes all states that can be reached from states in }{Q}_r^k\text{ by a single transition.} \\ \text{By repeat }{Q}_r^{k+1}\to Q_r^k\text{ until }k=0 \\ \text{We prove }(\forall i\ge 0)(Q_r^i\text{ is the set of all reachable states from }{q}_0\text{ using paths of length }i) \end{gathered}$$

8.b

8.c

$$\begin{gathered} \text{Base case } \\ {Q}_r^0=\{q_0\} \\ \text{Inductive Step} \\ {q}_0=Q_r^0\text{ by definition} \\ \text{Assume }(\forall i\ge 0)(q_0\in Q_r^i) \\ {Q}_r^{i+1}=Q_r^i\cup \{q\in Q|\exists p\in Q_r^i,\exists a\in \Sigma ,q=\delta (p,a)\} \\ \text{We can see it will repeat }{Q}_r^{i+1}\cup Q_r^i\text{ until }i=0\text{ which will union }{q}_0 \\ \text{Then }(\forall i\ge 0)(q_0\in Q_r^i) \end{gathered}$$

8.d

$M$ is DFA by definition

$M_r$ is base on $M$ but modify $\delta$ function and remove some state and final state. So it still a DFA

8.e

$$\begin{gathered} Q_r=\text{the state that can reach by init state} \\ F\cap Q_r=\text{only remain the final state can be reach by init state} \\ \text{since the state cant be reach by init state remove it will not change the language} \end{gathered}$$

9.a

Each symbols need 2 state to record is even or odd state and additional one state for init state; total 2n+1 state.

9.b

Because DFA each state have determine result to next state by input. We need to know all symbols is even or odd in one state. So each symbols have two possible (even or odd) lead to $2^n$ state

9.c

10.a

prove $M_1\to M_3$ are morphism

$$\begin{gathered} h(q_{(0,1)})=q_{(0,2)} \\ (\forall q\in Q_1,\forall a\in \Sigma )(h({\delta }_1(q,a))={\delta }_2(h(q),a)) \end{gathered}$$

$$\begin{gathered} M_1\to M_2 \\ (\forall q\in Q_1,\forall a\in \Sigma )f({\delta }_1(q,a))={\delta }_2(f(q),a) \\ {M}_2\to M_3 \\ (\forall q\in Q_2,\forall a\in \Sigma )g({\delta }_2(q,a))={\delta }_3(g(q),a) \\ {M}_1\to M_3 \\ \begin{array}{rl}(\forall q\in Q_1,\forall a\in \Sigma )& g(f({\delta }_1(q,a)))={\delta }_3(g(f(q)),a)\\ (\forall q\in Q_1,\forall a\in \Sigma )& g({\delta }_2(f(q),a))={\delta }_3(g(f(q)),a)\\ (\forall q\in Q_2,\forall a\in \Sigma )& g({\delta }_2(q,a))={\delta }_3(g(q),a)\end{array} \\ {M}_1\to M_3\text{ are morphism} \end{gathered}$$

F-map

$$\begin{gathered} f(F_1)\subseteq F_2(f\text{ is F-map}) \\ g(F_2)\subseteq F_3(g\text{ is F-map}) \\ \text{Therefore }g(f(F_1))\subseteq F_3 \\ g\circ f\text{ is F-map too.} \end{gathered}$$

B-map

$$\begin{gathered} \begin{array}{rlr}{f}^{-1}(F_2)& \subseteq F_1& (f\text{ is B-map})\\ g^{-1}(F_3)& \subseteq F_2& (g\text{ is B-map})\end{array} \\ \text{Therefore }{f}^{-1}(g^{-1}(F_3))\subseteq F_1 \\ g\circ f\text{ is B-map too.} \end{gathered}$$

10.b

$$\begin{gathered} \begin{array}{rl}{\hat{\delta }}_2(h(q),w_n)& =h({\hat{\delta }}_1(q,w_n))\\ {\delta }_2({\hat{\delta }}_2(h(q),w_{n-1}),a)& =h({\delta }_1({\hat{\delta }}_1(q,w_{n-1}),a))\\ {\delta }_2({\hat{\delta }}_2(h(q),w_{n-1}),a)& ={\delta }_2(h({\hat{\delta }}_1(q,w_{n-1})),a)\\ {\hat{\delta }}_2(h(q),w_{n-1})& =h({\hat{\delta }}_1(q,w_{n-1}))\end{array} \\ \text{By repeat this until }|w|=1\text{ make }{\hat{\delta }}_2(q,w)={\delta }_2(q,w) \\ \text{We prove that }(\forall q\in Q_1,\forall w\in {\Sigma }^{\ast })(h({\hat{\delta }}_1(q,w))={\hat{\delta }}_2(h(q),w)) \end{gathered}$$

10.c

$$\begin{gathered} \text{If is proper homomorphism then }{h}^{-1}(F_2)=F_1 \\ (\forall q\in Q_1,\forall a\in \Sigma )(h({\delta }_1(q,a))={\delta }_2(h(q),a)) \\ \text{Therefore }L(M_1)=L(M_2) \end{gathered}$$