formal_language_HW1.pdf
digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = doublecircle]; q1 node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q0 [ label = "0" ]; q0 -> q1 [ label = "1" ]; q1 -> q2 [ label = "0" ]; q2 -> q2 [ label = "1" ]; q2 -> q1 [ label = "0" ]; q1 -> q0 [ label = "1" ]; } digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = doublecircle]; q0,q1,q2; node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q0 [ label = "0" ]; q0 -> q1 [ label = "1" ]; q1 -> q0 [ label = "0" ]; q1 -> q2 [ label = "1" ]; q2 -> q2 [ label = "1" ]; q2 -> q3 [ label = "0" ]; q3 -> q3 [ label = "0,1" ]; } digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = doublecircle]; q0,q1; node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q1 [ label = "1" ]; q0 -> q2 [ label = "0" ]; q1 -> q0 [ label = "0,1" ]; q2 -> q2 [ label = "0,1" ]; } digraph finite_state_machine { rankdir=LR; layout=dot; size="100,100" node [shape = doublecircle]; q20,q21,q22; node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q00 [ label = "start" ]; q00 -> q10 [ label = "1" ];//1 0 q10 -> q20 [ label = "1" ];//2 0 q20 -> q20 [ label = "1" ]; q00 -> q01 [ label = "0" ];//0 1 q01 -> q02 [ label = "0" ];//0 2 q10 -> q11 [ label = "0" ];//1 1 q01 -> q11 [ label = "1" ]; q20 -> q21 [ label = "0" ];//2 1 q11 -> q21 [ label = "1" ]; q21 -> q21 [ label = "1" ]; q02 -> q12 [ label = "1" ];//1 2 q11 -> q12 [ label = "0" ]; q21 -> q22 [ label = "0" ];//2 2 q12 -> q22 [ label = "1" ]; q22 -> q22 [ label = "1" ]; q20 -> qn [ label = "0" ]; q21 -> qn [ label = "0" ]; q22 -> qn [ label = "0" ]; qn -> qn [ label = "0,1" ]; } digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = doublecircle]; q0; node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q0 [ label = "0" ]; q0 -> q1 [ label = "1" ]; q1 -> q1 [ label = "0,1" ]; } Q 1 = a Q 2 ∪ b Q 1 = b ∗ a Q 2 Q 2 = a Q 2 ∪ b Q 0 = a ∗ b Q 0 Q 0 = b Q 1 ∪ a Q 0 ∪ ϵ = a ∗ b Q 1 ∪ ϵ = a ∗ b ( b ∗ a Q 2 ) ∪ ϵ = a ∗ b b ∗ a ( a ∗ b Q 0 ) ∪ ϵ = a ∗ b + a + b Q 0 ∪ ϵ = ( a ∗ b + a + b ) ∗ ∪ ϵ = ( a ∗ b + a + b ) ∗ \begin{aligned}
Q_1&=a Q_2 \cup b Q_1 =b^*aQ_2\\
Q_2&=a Q_2 \cup b Q_0= a^*bQ_0\\
\\
Q_0&=b Q_1 \cup aQ_0 \cup \epsilon\\
&=a^*bQ_1 \cup \epsilon\\
&=a^*b(b^*aQ_2) \cup \epsilon\\
&=a^*bb^*a(a^*bQ_0) \cup \epsilon\\
&=a^*b^+a^+bQ_0 \cup \epsilon\\
&=(a^*b^+a^+b)^* \cup \epsilon\\
&=(a^*b^+a^+b)^*\\
\end{aligned}
% R=(a^* b^+a^+b)^\ast \cup \epsilon Q 1 Q 2 Q 0 = a Q 2 ∪ b Q 1 = b ∗ a Q 2 = a Q 2 ∪ b Q 0 = a ∗ b Q 0 = b Q 1 ∪ a Q 0 ∪ ϵ = a ∗ b Q 1 ∪ ϵ = a ∗ b ( b ∗ a Q 2 ) ∪ ϵ = a ∗ b b ∗ a ( a ∗ b Q 0 ) ∪ ϵ = a ∗ b + a + b Q 0 ∪ ϵ = ( a ∗ b + a + b ) ∗ ∪ ϵ = ( a ∗ b + a + b ) ∗ R = ( ( a ∗ ∪ b ) b ( b b ) ∗ a ) ∗ R=((a^*\cup b)b (bb)^*a )^* R = (( a ∗ ∪ b ) b ( bb ) ∗ a ) ∗ digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = doublecircle]; q2; node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q0 [ label = "0" ]; q0 -> q1 [ label = "1" ]; q1 -> q1 [ label = "1" ]; q1 -> q2 [ label = "0" ]; q2 -> q1 [ label = "1" ]; q2 -> q0 [ label = "0" ]; } digraph finite_state_machine { rankdir=LR; size="10,10" node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q0 [ label = "0" ]; q0 -> q1 [ label = "1" ]; q1 -> q1 [ label = "1" ]; q1 -> q2 [ label = "0" ]; q2 -> q0 [ label = "0" ]; q2 -> q3 [ label = "1" ]; q3 -> q2 [ label = "0" ]; node [shape = doublecircle]; q4; q3 -> q4 [ label = "1" ]; q4 -> q4 [ label = "0,1" ]; } digraph finite_state_machine { rankdir=LR; size="15,15" node [shape = circle]; node [shape=plaintext] s; s [label=""]; node [shape = doublecircle]; q3,q5; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q1 [ label = "ϵ" ]; q0 -> q2 [ label = "ϵ" ]; q1 -> q3 [ label = "1" ]; q1 -> q1 [ label = "0" ]; q3 -> q1 [ label = "1" ]; q3 -> q3 [ label = "0" ]; q2 -> q4 [ label = "0"] q2 -> q2 [ label = "1"] q4 -> q5 [ label = "0"] q4 -> q4 [ label = "1"] q5 -> q6 [ label = "0,1"] q6 -> q6 [ label = "0,1"] } digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = doublecircle]; q1,q2; node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q2 [ label = "0" ]; q0 -> q1 [ label = "1" ]; q1 -> q1 [ label = "0,1" ]; q2 -> q2 [ label = "0" ]; q2 -> q3 [ label = "1" ]; q3 -> q2 [ label = "0" ]; } digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = doublecircle]; q0,q3,q4; node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q2 [ label = "0" ]; q0 -> q1 [ label = "1" ]; q1 -> q2 [ label = "0" ]; q1 -> q3 [ label = "1" ]; q3 -> q2 [ label = "0" ]; q3 -> q4 [ label = "1" ]; q4 -> q2 [ label = "0" ]; q4 -> q3 [ label = "1" ]; } R = ( 0 ∗ 1 + ) 3 Σ ∗ R=(0^* 1^+ )^3\Sigma^* R = ( 0 ∗ 1 + ) 3 Σ ∗ ref
R = ( 1 + 01 + 01 ∗ ) ∪ ( 1 ∗ 01 + 01 + ) ∪ ( 11 + 01 ∗ 01 ∗ ) ∪ ( 1 ∗ 01 ∗ 011 + ) ∪ ( 011 + 0 ) R=(1^+ 0 1^+ 0 1^*)\cup(1^* 0 1^+ 0 1^+)\cup(11^+ 01^*01^*)\cup(1^*01^*011^+)\cup(011^+0) R = ( 1 + 0 1 + 0 1 ∗ ) ∪ ( 1 ∗ 0 1 + 0 1 + ) ∪ ( 1 1 + 0 1 ∗ 0 1 ∗ ) ∪ ( 1 ∗ 0 1 ∗ 01 1 + ) ∪ ( 01 1 + 0 ) R = ( 1 ∘ Σ ) ∗ R=( 1 \circ \Sigma )^* R = ( 1 ∘ Σ ) ∗ If L L L min ( L ) \min(L) min ( L ) min ( L ) \min(L) min ( L ) L L L
for example
L = ( a b ∪ a b c ∪ a b c d ∪ a c ) L=(ab\cup abc\cup abcd \cup ac ) L = ( ab ∪ ab c ∪ ab c d ∪ a c ) digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = doublecircle]; q2,q3,q4,q5; node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q1 [ label = "a" ]; q1 -> q2 [ label = "b" ]; q1 -> q5 [ label = "c" ]; q2 -> q3 [ label = "c" ]; q3 -> q4 [ label = "d" ]; } m i n ( L ) = ( a b ∪ a c ) min(L)=(ab\cup ac ) min ( L ) = ( ab ∪ a c ) digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = doublecircle]; q2,q5; node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q1 [ label = "a" ]; q1 -> q2 [ label = "b" ]; q1 -> q5 [ label = "c" ]; } L ∗ = ⋃ i ∈ N L i L ∗ ∗ = ( ⋃ i ∈ N L i ) ∗ = ⋃ j ∈ N ( ⋃ i ∈ N L i ) j = ⋃ j ∈ N ⋃ i ∈ N L i j = ⋃ i j ∈ N L i j = L ∗ \begin{aligned}
L^*&=\bigcup_{i \in \N}L^i\\
L^{**}&=(\bigcup_{i \in \N}L^i)^*\\
&=\bigcup_{j \in \N}(\bigcup_{i \in \N}L^i)^j\\
&=\bigcup_{j \in \N}\bigcup_{i \in \N}L^{ij}\\
&=\bigcup_{ij \in \N}L^{ij}\\
&=L^*\\
\end{aligned} L ∗ L ∗∗ = i ∈ N ⋃ L i = ( i ∈ N ⋃ L i ) ∗ = j ∈ N ⋃ ( i ∈ N ⋃ L i ) j = j ∈ N ⋃ i ∈ N ⋃ L ij = ij ∈ N ⋃ L ij = L ∗ L ∗ L ∗ = ( L + ∪ ϵ ) ( L + ∪ ϵ ) = L L + ∪ L + ∪ ϵ = L ∗ \begin{aligned}
L^*L^*&=(L^+\cup \epsilon)(L^+\cup \epsilon)\\
&=LL^+\cup L^+ \cup \epsilon\\
&=L^*
\end{aligned} L ∗ L ∗ = ( L + ∪ ϵ ) ( L + ∪ ϵ ) = L L + ∪ L + ∪ ϵ = L ∗ A is a finite language, then it contains a finite number of strings a 0 , a 1 , ⋯ , a n The language { a i } consisting of a single literal string a i is regular The union of a finite number of regular languages is also regular. Therefore A = a 0 , a 1 , ⋯ , a n is regular 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} A is a finite language, then it contains a finite number of strings a 0 , a 1 , ⋯ , a n The language { a i } consisting of a single literal string a i is regular The union of a finite number of regular languages is also regular. Therefore A = a 0 , a 1 , ⋯ , a n is regular ref
A ⊆ B A = { a n b n ∣ n ∈ N 0 } B = { ( a ∪ b ) n ∣ n ∈ N 0 } A \subseteq B\\
A=\{a^nb^n|n\in \N_0\}\\
B=\{(a\cup b)^n|n\in \N_0\}\\ A ⊆ B A = { a n b n ∣ n ∈ N 0 } B = {( a ∪ b ) n ∣ n ∈ N 0 } B ⊆ A A = { a n b n ∣ n ∈ N 0 } B = { w ∣ w = a b } B \subseteq A\\
A=\{a^nb^n|n\in \N_0\}\\
B=\{w|w=ab \}\\ B ⊆ A A = { a n b n ∣ n ∈ N 0 } B = { w ∣ w = ab } L ( 1 3 ) = { w ∣ w 3 ∈ L }
L^{(\frac{1}{3})}=\{w|w^3\in L\}\\ L ( 3 1 ) = { w ∣ w 3 ∈ L } L ( 1 3 ) mean all the solution that in L that can divide to 3 exact same part L^{(\frac{1}{3})} \text{ mean all the solution that in } L \text{ that can divide to 3 exact same part}\\
L ( 3 1 ) mean all the solution that in L that can divide to 3 exact same part L ( 3 ) = { w 3 ∣ w ∈ L } If L = { a b ∗ , b } L ( 3 ) = { ( a b ∗ ) 3 , b b b } = { a b ∗ a b ∗ a b ∗ , b b b } w 3 = w ⏟ x w ⏟ y w ⏟ z By pumping lemma ∣ y ∣ ≥ 1 ∣ x y ∣ ≤ p ( ∀ k ≥ 0 ) ( x y k z ∈ L ) But x y 0 z = w w ∉ L Therefor this is not regular languages L^{(3)}=\{w^3|w\in L\}\\
% \text{since } L \text{ is regular so is } L^3.\text{(regular closure)}
\text{If }L=\{ab^*,b\}\\
L^{(3)}=\{(ab^*)^3,bbb\}=\{ab^*ab^*ab^*,bbb\}\\ \\
w^3=\underbrace{w}_{x} \ \ \underbrace{w}_{y} \ \ \underbrace{w}_{z} \\
\text{By pumping lemma}\\
|y|\geq 1\\
|xy| \leq p\\
(\forall k \geq 0)(xy^kz \in L )\\
\text{But }xy^0z=ww \notin L \\
\text{Therefor this is not regular languages} L ( 3 ) = { w 3 ∣ w ∈ L } If L = { a b ∗ , b } L ( 3 ) = {( a b ∗ ) 3 , bbb } = { a b ∗ a b ∗ a b ∗ , bbb } w 3 = x w y w z w By pumping lemma ∣ y ∣ ≥ 1 ∣ x y ∣ ≤ p ( ∀ k ≥ 0 ) ( x y k z ∈ L ) But x y 0 z = ww ∈ / L Therefor this is not regular languages ref (Formal definition)
If L L L
Divide a DFA to k k k
L 1 ∞ = L 1 ∩ L 1 2 ⋯ ∩ L 1 ∞ since L is regular so is the L 1 n L ∞ are regular because it is interest of L 1 n 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}}\\ L ∞ 1 = L 1 ∩ L 2 1 ⋯ ∩ L ∞ 1 since L is regular so is the L n 1 L ∞ are regular because it is interest of L n 1 L = ⋃ k ≤ 1 L 1 k L is regular by union closure
\sqrt{L} =\bigcup_{k\leq 1} L^{\frac{1}{k}}\\
\sqrt{L}\text{ is regular by union closure} L = k ≤ 1 ⋃ L k 1 L is regular by union closure not regular
L = { w c w ∣ w ∈ { a , b } ∗ } L=\{wcw| w\in \{a,b\}^*\} L = { w c w ∣ w ∈ { a , b } ∗ } w c w = ( a ∪ b ) i c ( a ∪ b ) i ( a ∪ b ) i c ( a ∪ b ) j = ( a ∪ b ) p − i ⏟ x ( a ∪ b ) i ⏟ y c ( a ∪ b ) p ⏟ z and i > 0 By pumping lemma ∣ y ∣ ≥ 1 ∣ x y ∣ ≤ p ( ∀ k ≥ 0 ) ( x y k z ∈ L ) But x y 0 z = ( a ∪ b ) p − i c ( a ∪ b ) p ∉ L Therefor this is not regular languages wcw=(a\cup b)^i c(a\cup b)^i\\
(a\cup b)^i c(a\cup b)^j=\underbrace{(a\cup b)^{p-i}}_{x} \ \ \underbrace{(a\cup b)^{i}}_{y} \ \ \underbrace{c(a\cup b)^{p}}_{z} \text{ and }i>0\\
\text{By pumping lemma}\\
|y|\geq 1\\
|xy| \leq p\\
(\forall k \geq 0)(xy^kz \in L )\\
\text{But }xy^0z=(a\cup b)^{p-i}c(a\cup b)^p \notin L \\
\text{Therefor this is not regular languages}
w c w = ( a ∪ b ) i c ( a ∪ b ) i ( a ∪ b ) i c ( a ∪ b ) j = x ( a ∪ b ) p − i y ( a ∪ b ) i z c ( a ∪ b ) p and i > 0 By pumping lemma ∣ y ∣ ≥ 1 ∣ x y ∣ ≤ p ( ∀ k ≥ 0 ) ( x y k z ∈ L ) But x y 0 z = ( a ∪ b ) p − i c ( a ∪ b ) p ∈ / L Therefor this is not regular languages L = { x y ∣ x , y ∈ { a , b } ∗ and ∣ x ∣ = ∣ y ∣ } L=\{xy| x,y\in \{a,b\}^* \text{ and } |x|=|y|\} L = { x y ∣ x , y ∈ { a , b } ∗ and ∣ x ∣ = ∣ y ∣ } x y = { a , b } p { a , b } p x and y is regular languages w is regular languages by closure of concatenate xy=\{a,b\}^p\{a,b\}^p\\
x \text{ and } y \text{ is regular languages }\\
w\text{ is regular languages by closure of concatenate} x y = { a , b } p { a , b } p x and y is regular languages w is regular languages by closure of concatenate L = { a n ∣ n is a prime number } L = \{a^n | n \text{ is a prime number}\} L = { a n ∣ n is a prime number } a p = a p − j − i ⏟ x a i ⏟ y a j ⏟ z ∣ y ∣ ≥ 1 ∣ x y ∣ ≤ p ( ∀ k ≥ 0 ) ( x y k z ∈ L ) But x y 0 z = a p − j − i a j = a p − i ∉ L Therefor this is not regular languages a^p=\underbrace{a^{p-j-i}}_x \underbrace{a^i}_y \underbrace{a^{j}}_z\\
|y|\geq 1 \\
|xy| \leq p\\
(\forall k \geq 0)(xy^k z \in L )\\
\text{But }xy^0z=a^{p-j-i}a^{j}=a^{p-i}\notin L \\
\text{Therefor this is not regular languages} a p = x a p − j − i y a i z a j ∣ y ∣ ≥ 1 ∣ x y ∣ ≤ p ( ∀ k ≥ 0 ) ( x y k z ∈ L ) But x y 0 z = a p − j − i a j = a p − i ∈ / L Therefor this is not regular languages L = { a m b n ∣ g c d ( m , n ) = 17 } L = \{a^mb^n | gcd(m, n) = 17\} L = { a m b n ∣ g c d ( m , n ) = 17 } j , k ∈ N and g c d ( j , k ) = 1 then a m b n = a 17 j b 17 k a m b n = a 17 j − i ⏟ x a i ⏟ y b 17 k ⏟ z ∣ y ∣ ≥ 1 ∣ x y ∣ ≤ p ( ∀ k ≥ 0 ) ( x y k z ∈ L ) But x y 0 z = a 17 j − i b 17 k ∉ L Therefor this is not regular languages j,k\in \N \text{ and }gcd(j,k)=1 \\
\text{ then }a^mb^n=a^{17j}b^{17k}\\
a^mb^n=\underbrace{a^{17j-i}}_x \underbrace{a^i}_y \underbrace{b^{17k}}_z\\
|y|\geq 1 \\
|xy| \leq p\\
(\forall k \geq 0)(xy^kz \in L )\\
\text{But }xy^0z=a^{17j-i}b^{17k}\notin L \\
\text{Therefor this is not regular languages} j , k ∈ N and g c d ( j , k ) = 1 then a m b n = a 17 j b 17 k a m b n = x a 17 j − i y a i z b 17 k ∣ y ∣ ≥ 1 ∣ x y ∣ ≤ p ( ∀ k ≥ 0 ) ( x y k z ∈ L ) But x y 0 z = a 17 j − i b 17 k ∈ / L Therefor this is not regular languages Base case i = 0 , Q r 0 = { q 0 } This is trivially true since the only path of length 0 is the path that starts and ends at q 0 Inductive Step Assume that for some k ≥ 0 , Q r k is the set of all reachable states from q 0 using paths of length k . By definition, Q r k + 1 includes all states that can be reached from states in Q r k by a single transition. By repeat Q r k + 1 → Q r k until k = 0 We prove ( ∀ i ≥ 0 ) ( Q r i is the set of all reachable states from q 0 using paths of length i ) % \begin{aligned}
% \begin{split}
\text{Base case } \\
i=0 ,Q^{0}_r=\{ 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}\\
% We aim to show that Qk+1rQk+1r represents the set of all reachable states from q0q0 using paths of length k+1k+1.
\text{Assume that for some }k\geq 0, Q^k_r \text{ is the set of all reachable states from } q_0 \text{ using paths of length }k.\\
\text{By definition, }Q^{k+1}_r \text{ includes all states that can be reached from states in } Q^k_r \text{ by a single transition.}\\ \\
\text{By repeat } Q^{k+1}_r \rightarrow Q^{k}_r \text{ until }k=0\\
\text{We prove } (\forall i\geq 0) (Q^i_r\text{ is the set of all reachable states from }q_0\text{ using paths of length } i)
% \end{split}
% \end{aligned} Base case i = 0 , Q r 0 = { q 0 } This is trivially true since the only path of length 0 is the path that starts and ends at q 0 Inductive Step Assume that for some k ≥ 0 , Q r k is the set of all reachable states from q 0 using paths of length k . By definition, Q r k + 1 includes all states that can be reached from states in Q r k by a single transition. By repeat Q r k + 1 → Q r k until k = 0 We prove ( ∀ i ≥ 0 ) ( Q r i is the set of all reachable states from q 0 using paths of length i ) digraph finite_state_machine { rankdir=LR; size="8,5" node [shape = doublecircle]; q0 node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> q0 [ label = "start" ]; q0 -> q1 [ label = "0,1" ]; q1 -> q2 [ label = "0,1" ]; q2 -> q0 [ label = "0,1" ]; } Base case Q r 0 = { q 0 } Inductive Step q 0 = Q r 0 by definition Assume ( ∀ i ≥ 0 ) ( q 0 ∈ Q r i ) Q r i + 1 = Q r i ∪ { q ∈ Q ∣ ∃ p ∈ Q r i , ∃ a ∈ Σ , q = δ ( p , a ) } We can see it will repeat Q r i + 1 ∪ Q r i until i = 0 which will union q 0 Then ( ∀ i ≥ 0 ) ( q 0 ∈ Q r i ) \text{Base case } \\
Q^{0}_r=\{q_0\}\\
\text{Inductive Step}\\
q_0 = Q^0_r\text{ by definition}\\
\text{Assume } (\forall i \geq 0) (q_0\in Q^i_r)\\
Q^{i+1}_r=Q^i_r \cup \{ q\in Q | \exist p \in Q^i_r, \exist a \in \Sigma ,q = \delta (p,a)\}\\
\text{We can see it will repeat } Q^{i+1}_r \cup Q^{i}_r \text{ until }i=0 \text{ which will union }q_0\\
\text{Then } (\forall i \geq 0) (q_0\in Q^i_r)\\
Base case Q r 0 = { q 0 } Inductive Step q 0 = Q r 0 by definition Assume ( ∀ i ≥ 0 ) ( q 0 ∈ Q r i ) Q r i + 1 = Q r i ∪ { q ∈ Q ∣∃ p ∈ Q r i , ∃ a ∈ Σ , q = δ ( p , a )} We can see it will repeat Q r i + 1 ∪ Q r i until i = 0 which will union q 0 Then ( ∀ i ≥ 0 ) ( q 0 ∈ Q r i ) M M M
M r M_r M r M M M δ \delta δ
Q r = the state that can reach by init state F ∩ Q r = only remain the final state can be reach by init state since the state cant be reach by init state remove it will not change the language 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}\\
Q r = the state that can reach by init state F ∩ Q r = only remain the final state can be reach by init state since the state cant be reach by init state remove it will not change the language Each symbols need 2 state to record is even or odd state and additional one state for init state; total 2n+1 state.
digraph finite_state_machine { rankdir=LR; size="10,10" node [shape = doublecircle]; Q1_1,Q2_1, Q3_1 ,Qn_1; node [shape=plaintext] s; s [label=""]; node [shape = circle]; s -> Q0 [ label = "start" ]; Q0 -> Q1_1 [ label = "a1" ]; Q0 -> Q2_1 [ label = "a2" ]; Q0 -> Q3_1 [ label = "a3" ]; Q0 -> Qn_1 [ label = "an" ]; Q1_1 -> Q1_2 [ label = "a1" ]; Q1_2 -> Q1_1 [ label = "a1" ]; Q2_1 -> Q2_2 [ label = "a2" ]; Q2_2 -> Q2_1 [ label = "a2" ]; Q3_1 -> Q3_2 [ label = "a3" ]; Q3_2 -> Q3_1 [ label = "a3" ]; Qn_1 -> Qn_2 [ label = "an" ]; Qn_2 -> Qn_1 [ label = "an" ]; } 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 2^n 2 n
h ( q ( 0 , 1 ) ) = q ( 0 , 2 ) ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ) ( h ( δ 1 ( q , a ) ) = δ 2 ( h ( q ) , a ) ) h(q_{(0,1)})=q_{(0,2)}\\
\text{}
(\forall q\in Q_1,\forall a\in \Sigma)(h(\delta_1(q,a)) =\delta_2(h(q),a))\\
h ( q ( 0 , 1 ) ) = q ( 0 , 2 ) ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ) ( h ( δ 1 ( q , a )) = δ 2 ( h ( q ) , a )) M 1 → M 2 ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ) f ( δ 1 ( q , a ) ) = δ 2 ( f ( q ) , a ) M 2 → M 3 ( ∀ q ∈ Q 2 , ∀ a ∈ Σ ) g ( δ 2 ( q , a ) ) = δ 3 ( g ( q ) , a ) M 1 → M 3 ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ) g ( f ( δ 1 ( q , a ) ) ) = δ 3 ( g ( f ( q ) ) , a ) ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ) g ( δ 2 ( f ( q ) , a ) ) = δ 3 ( g ( f ( q ) ) , a ) ( ∀ q ∈ Q 2 , ∀ a ∈ Σ ) g ( δ 2 ( q , a ) ) = δ 3 ( g ( q ) , a ) M 1 → M 3 are morphism M_1 \rightarrow M_2\\
(\forall q\in Q_1,\forall a\in \Sigma)f(\delta_1(q,a)) =\delta_2(f(q),a)\\
M_2 \rightarrow M_3\\
(\forall q\in Q_2,\forall a\in \Sigma)g(\delta_2(q,a)) =\delta_3(g(q),a)\\
M_1 \rightarrow M_3\\
\begin{aligned}
(\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{aligned}\\
M_1 \rightarrow M_3 \text{ are morphism}
% \\ \text{} \\
% g(\delta_2(f(q),a))=\delta_3(g(f(q)),a)\\
% \circ
% (\forall q\in Q_2,\forall a\in \Sigma)(g(\delta_2(q,a)) =\delta_3(g(q),a))\\
% (\forall q\in Q_1,\forall a\in \Sigma)(g(\delta_2(f(q),a)) =\delta_3(g(f(q)),a))\\
% \begin{aligned}
% \delta_1(q_{(n,1)},a)&=h^{-1}(\delta_2(h(q_{(n,1)}),a))\\
% &=\delta_2(q_{(n,2)},a)\\
% \end{aligned} M 1 → M 2 ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ) f ( δ 1 ( q , a )) = δ 2 ( f ( q ) , a ) M 2 → M 3 ( ∀ q ∈ Q 2 , ∀ a ∈ Σ ) g ( δ 2 ( q , a )) = δ 3 ( g ( q ) , a ) M 1 → M 3 ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ) ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ) ( ∀ q ∈ Q 2 , ∀ a ∈ Σ ) g ( f ( δ 1 ( q , a ))) = δ 3 ( g ( f ( q )) , a ) g ( δ 2 ( f ( q ) , a )) = δ 3 ( g ( f ( q )) , a ) g ( δ 2 ( q , a )) = δ 3 ( g ( q ) , a ) M 1 → M 3 are morphism f ( F 1 ) ⊆ F 2 ( f is F-map ) g ( F 2 ) ⊆ F 3 ( g is F-map ) Therefore g ( f ( F 1 ) ) ⊆ F 3 g ∘ f is F-map too. 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.} f ( F 1 ) ⊆ F 2 ( f is F-map ) g ( F 2 ) ⊆ F 3 ( g is F-map ) Therefore g ( f ( F 1 )) ⊆ F 3 g ∘ f is F-map too. f − 1 ( F 2 ) ⊆ F 1 ( f is B-map ) g − 1 ( F 3 ) ⊆ F 2 ( g is B-map ) Therefore f − 1 ( g − 1 ( F 3 ) ) ⊆ F 1 g ∘ f is B-map too. \begin{aligned}
f^{-1}(F_2)&\subseteq F_1 &(f \text{ is B-map})\\
% F_2&\subseteq f(F_1) &(f \text{ is B-map})\\
g^{-1}(F_3)&\subseteq F_2 &(g \text{ is B-map})\\
% F_3&\subseteq g(F_2) &(g \text{ is B-map})\\
\end{aligned}
{}\\
\text{Therefore }f^{-1}(g^{-1}(F_3))\subseteq F_1\\
g\circ f \text{ is B-map too.} f − 1 ( F 2 ) g − 1 ( F 3 ) ⊆ F 1 ⊆ F 2 ( f is B-map ) ( g is B-map ) Therefore f − 1 ( g − 1 ( F 3 )) ⊆ F 1 g ∘ f is B-map too. δ ^ 2 ( h ( q ) , w n ) = h ( δ ^ 1 ( q , w n ) ) δ 2 ( δ ^ 2 ( h ( q ) , w n − 1 ) , a ) = h ( δ 1 ( δ ^ 1 ( q , w n − 1 ) , a ) ) δ 2 ( δ ^ 2 ( h ( q ) , w n − 1 ) , a ) = δ 2 ( h ( δ ^ 1 ( q , w n − 1 ) ) , a ) δ ^ 2 ( h ( q ) , w n − 1 ) = h ( δ ^ 1 ( q , w n − 1 ) ) By repeat this until ∣ w ∣ = 1 make δ ^ 2 ( q , w ) = δ 2 ( q , w ) We prove that ( ∀ q ∈ Q 1 , ∀ w ∈ Σ ∗ ) ( h ( δ ^ 1 ( q , w ) ) = δ ^ 2 ( h ( q ) , w ) )
% h(\delta_1(q,w_1)) =\delta_2(h(q),w_1)\\
\text{}\\
\begin{aligned}
% h(\delta_1(\delta_1(q,w_1),w_2))&=\delta_2(\delta_2(h(q),w_1),w_2)\\
\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{aligned}\\
\text{By repeat this until } |w|=1 \text{ make }\hat{\delta}_2(q,w)=\delta_2(q,w)\\
% h(\delta_1(q,w_1)) =\delta_2(h(q),w_1)\\
\text{}\\
\text{We prove that }
(\forall q\in Q_1,\forall w\in \Sigma^{*})(h(\hat{\delta}_1(q,w)) =\hat{\delta}_2(h(q),w))\\ δ ^ 2 ( h ( q ) , w n ) δ 2 ( δ ^ 2 ( h ( q ) , w n − 1 ) , a ) δ 2 ( δ ^ 2 ( h ( q ) , w n − 1 ) , a ) δ ^ 2 ( h ( q ) , w n − 1 ) = h ( δ ^ 1 ( q , w n )) = h ( δ 1 ( δ ^ 1 ( q , w n − 1 ) , a )) = δ 2 ( h ( δ ^ 1 ( q , w n − 1 )) , a ) = h ( δ ^ 1 ( q , w n − 1 )) By repeat this until ∣ w ∣ = 1 make δ ^ 2 ( q , w ) = δ 2 ( q , w ) We prove that ( ∀ q ∈ Q 1 , ∀ w ∈ Σ ∗ ) ( h ( δ ^ 1 ( q , w )) = δ ^ 2 ( h ( q ) , w )) If is proper homomorphism then h − 1 ( F 2 ) = F 1 ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ) ( h ( δ 1 ( q , a ) ) = δ 2 ( h ( q ) , a ) ) Therefore L ( M 1 ) = L ( M 2 ) \text{If is proper homomorphism then }h^{-1}(F_2)=F_1\\
% (\forall q\in Q_1,\forall w\in \Sigma^{*})(h(\hat{\delta}_1(q,w)) =\hat{\delta}_2(h(q),w))(M_1\rightarrow M_2 \text{ is a morphism})\\
(\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)\\ If is proper homomorphism then h − 1 ( F 2 ) = F 1 ( ∀ q ∈ Q 1 , ∀ a ∈ Σ ) ( h ( δ 1 ( q , a )) = δ 2 ( h ( q ) , a )) Therefore L ( M 1 ) = L ( M 2 )