math

yeah the math stuff

Calculus

tags math calculus

Differential

$$f^{\prime }(x)=\underset{h\to 0}{\lim }\frac{f(x+h)+f(x)}{h}$$ $$f^{\prime }(x)=\frac{d}{dx}f(x)$$ $$\frac{d}{dx}f(x)g(x)=f^{\prime }(x)g(x)+f(x)g^{\prime }(x)$$ $$\frac{d}{dx}\frac{f(x)}{g(x)}=\frac{f^{\prime }(x)g(x)+f(x)g^{\prime }(x)}{g(x{)}^2}$$ $$\frac{d}{dx}f(g(x))=f^{\prime }(g(x))\times g^{\prime }(x)$$

example

$$\frac{d}{dx}cos(x)=-sin(x)$$ $$\frac{d}{dx}tan(x)=sec(x{)}^2$$ $$\frac{d}{dx}cot(x)=csc(x{)}^2$$ $$\frac{d}{dx}si{n}^{-1}(x)=\frac{1}{\sqrt{1-x^2}}$$ $$\frac{d}{dx}co{s}^{-1}(x)=\frac{-1}{\sqrt{1-x^2}}$$ $$\frac{d}{dx}ta{n}^{-1}(x)=\frac{1}{1+x^2}$$

intergrant

$$\begin{gathered} g(x)=\underset{{}_{k(x)}}{{\int }^{h(x)}}f(x)dx \\ {g}^{\prime }(x)=f(h(x))h^{\prime }(x)-f(k(x))k^{\prime }(x) \end{gathered}$$ $$\int f(x)dg(x)=f(x)g(x)-\int g(x)df(x)$$

example

$$\int e^{f(x)}dx=\frac{e^{f(x)}}{f^{\prime }(x)}+c$$ $$\int \ln (x)dx=x\ln (x)-x+c$$ $$\int \frac{1}{x}dx=\ln (x)+c$$ $$\int sin(x)dx=-cos(x)+c$$ $$\int tan(x)dx=-\ln (cos(x))+c$$ $$\int sec(x{)}^{2}dx=tan(x)+c$$ $$\int \frac{2x}{1+x^2}dx=\ln (1+x^2)+c$$

Taylor series 泰勒展開式

$$\begin{gathered} f^{(n)}(a)=f(x)在x=a的n次導數 \\ f(x)=\frac{f^{(0)}(a)}{0!}(x-a{)}^0+\frac{f^{(1)}(a)}{1!}(x-a{)}^1+\frac{f^{(2)}(a)}{2!}(x-a{)}^2\cdots \\ f(x)=\sum _{n=0}^{\infty }\frac{f^{(n)}(a)}{n!}(x-a{)}^n \end{gathered}$$

find sin(x) Taylor series

$$\begin{gathered} \begin{array}{rl}f(x)=sin(x)\to & f^0(x)=sin(x)\\ & f^1(x)=cos(x)\\ & f^2(x)=-sin(x)\\ & f^3(x)=-cos(x)\\ & f^4(x)=sin(x)=f^0(x)\end{array} \\ \text{if }a=0 \\ \begin{array}{rl}f(x)& =\sum _{n=0}^{\infty }\frac{f^{(n)}(a)}{n!}(x-a{)}^n\\ & =\sum _{n=0}^{\infty }\frac{sin(0)}{(4n+0)!}(x{)}^{4n}+\frac{cos(0)}{(4n+1)!}(x{)}^{4n+1}+\frac{-sin(0)}{(4n+2)!}(x{)}^{4n+2}+\frac{-cos(0)}{(4n+3)!}(x{)}^{4n+3}\\ & =\sum _{n=0}^{\infty }\frac{cos(0)}{(4n+1)!}(x{)}^{4n+1}+\frac{-cos(0)}{(4n+3)!}(x{)}^{4n+3}\\ & =\sum _{n=0}^{\infty }\frac{1}{(4n+1)!}(x{)}^{4n+1}+\frac{-1}{(4n+3)!}(x{)}^{4n+3}\\ sin(x)& =\sum _{n=0}^{\infty }\frac{(-1{)}^n}{(2n+1)!}(x{)}^{2n+1}\end{array} \end{gathered}$$

Formal Language

tags: math

link

automata

• DFA(Deterministic Finite Automation)
• NFA(Nondeterministic Finite Automation)
• PDA(Push Down Automation)

DFA / NFA

DFA

$$\begin{array}{rl}DFA& =(Q,\Sigma ,\delta ,q_0,F)\\ & Q=\text{state set}\\ & \Sigma =\text{input char domain(set)}\\ & \delta =\delta (Q,\Sigma )\to Q^{\prime }\\ & q_0=\text{start state}\\ & F=\text{accept state set}\end{array}$$

regular language

regular expression

$$\begin{array}{rl}\varnothing & =\text{empty set}\\ ϵ& =\text{empty expression}\\ \circ & =\text{concat}\\ R^k& =\underset{k\text{ times}}{\underbrace{R\circ R\circ \cdots \circ R}}\\ R^{+}& =R\circ R^{\ast }\\ R^{\ast }& =R^{+}\cup ϵ\end{array}$$

closure properties

$$\begin{gathered} L_1,L_2\text{ is regular language} \\ \text{operation}\{\begin{array}{l}{L}_1\cup L_2\\ L_1\cap L_2\\ \overline{L_1}\\ L_1\circ L_2\\ L^{\ast }\\ L_1-L_2=L_1\cap \overline{L_2}\\ \text{homomorphism}\end{array}\text{ is regular language} \end{gathered}$$

pumping lemma for regular languages

$$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}$$

DFA == regular language

For every NFA $N$ there is a regular expression $R$ such that $L(R)=L(N)$

L(q,p,k){w ∈ ${\Sigma }^{\ast }$ | there is a run of M on w from state q to state p and let passing through states set length < k}.

DFA to regular language

state removal method

brzozowski algebraic method

PDA

$$\begin{array}{rl}P& =(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)\\ & \begin{array}{rl}Q& =\text{state set}\\ \Sigma & =\text{input char domain(set)}\\ \Gamma & =\text{stack symbol set}\\ \delta & =\delta (Q,\Gamma ,\Sigma )\to (Q^{\prime },{\Gamma }^{\prime })\\ q_0& =\text{init state}\\ Z_0& =\text{init stack}\\ F& =\text{accept state set}\end{array}\end{array}$$

context free language

$$\begin{array}{rl}G& =(V,\Sigma ,P,S)\\ & \begin{array}{rl}V& =\text{state set}\\ \Sigma & =\text{input char domain(set)}\\ S& =\text{start variable}\\ P& =S\to S^{\prime }\end{array}\end{array}$$

$$L_1=\{a^n{b}^m{c}^{m+n}|n,m\in {\mathbb{N}}_0\}$$

$$\begin{gathered} \begin{array}{rl}G& =(V,\Sigma ,P,S)\\ & \begin{array}{rl}V& =\{S,A,B\}\\ \Sigma & =\{0,1\}\\ S& =\text{start variable}\\ P& =\{\begin{array}{ll}S& \to A\\ A& \to aAc\text{|}B\\ B& \to bBc\text{|}ϵ\end{array}\end{array}\end{array} \\ {L}_1=L(G) \end{gathered}$$

pumping lemma for CFL

closure properties

$$\begin{gathered} L_1,L_2\text{ is regular language} \\ \text{operation}\{\begin{array}{l}{L}_1\cup L_2\\ \overline{L_1}\\ L_1\circ L_2\\ L^{\ast }\\ L_1-L_2=L_1\cap \overline{L_2}\\ \text{homomorphism}\end{array}\text{ is regular language} \end{gathered}$$

Formal Language

tags: math

link

automata

• DFA(Deterministic Finite Automation)
• NFA(Nondeterministic Finite Automation)
• PDA(Push Down Automation)

DFA / NFA

DFA

$$\begin{array}{rl}DFA& =(Q,\Sigma ,\delta ,q_0,F)\\ & Q=\text{state set}\\ & \Sigma =\text{input char domain(set)}\\ & \delta =\delta (Q,\Sigma )\to Q^{\prime }\\ & q_0=\text{start state}\\ & F=\text{accept state set}\end{array}$$

regular language

regular expression

$$\begin{array}{rl}\varnothing & =\text{empty set}\\ ϵ& =\text{empty expression}\\ \circ & =\text{concat}\\ R^k& =\underset{k\text{ times}}{\underbrace{R\circ R\circ \cdots \circ R}}\\ R^{+}& =R\circ R^{\ast }\\ R^{\ast }& =R^{+}\cup ϵ\end{array}$$

closure properties

$$\begin{gathered} L_1,L_2\text{ is regular language} \\ \text{operation}\{\begin{array}{l}{L}_1\cup L_2\\ L_1\cap L_2\\ \overline{L_1}\\ L_1\circ L_2\\ L^{\ast }\\ L_1-L_2=L_1\cap \overline{L_2}\\ \text{homomorphism}\end{array}\text{ is regular language} \end{gathered}$$

pumping lemma for regular languages

$$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}$$

DFA == regular language

For every NFA $N$ there is a regular expression $R$ such that $L(R)=L(N)$

L(q,p,k){w ∈ ${\Sigma }^{\ast }$ | there is a run of M on w from state q to state p and let passing through states set length < k}.

DFA to regular language

state removal method

brzozowski algebraic method

PDA

$$\begin{array}{rl}P& =(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)\\ & \begin{array}{rl}Q& =\text{state set}\\ \Sigma & =\text{input char domain(set)}\\ \Gamma & =\text{stack symbol set}\\ \delta & =\delta (Q,\Gamma ,\Sigma )\to (Q^{\prime },{\Gamma }^{\prime })\\ q_0& =\text{init state}\\ Z_0& =\text{init stack}\\ F& =\text{accept state set}\end{array}\end{array}$$

context free language

$$\begin{array}{rl}G& =(V,\Sigma ,P,S)\\ & \begin{array}{rl}V& =\text{state set}\\ \Sigma & =\text{input char domain(set)}\\ S& =\text{start variable}\\ P& =S\to S^{\prime }\end{array}\end{array}$$

$$L_1=\{a^n{b}^m{c}^{m+n}|n,m\in {\mathbb{N}}_0\}$$

$$\begin{gathered} \begin{array}{rl}G& =(V,\Sigma ,P,S)\\ & \begin{array}{rl}V& =\{S,A,B\}\\ \Sigma & =\{0,1\}\\ S& =\text{start variable}\\ P& =\{\begin{array}{ll}S& \to A\\ A& \to aAc\text{|}B\\ B& \to bBc\text{|}ϵ\end{array}\end{array}\end{array} \\ {L}_1=L(G) \end{gathered}$$

pumping lemma for CFL

closure properties

$$\begin{gathered} L_1,L_2\text{ is regular language} \\ \text{operation}\{\begin{array}{l}{L}_1\cup L_2\\ \overline{L_1}\\ L_1\circ L_2\\ L^{\ast }\\ L_1-L_2=L_1\cap \overline{L_2}\\ \text{homomorphism}\end{array}\text{ is regular language} \end{gathered}$$

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}$$

tags math linear algebra

linear algebra

matrix

diagonal 對角 commutative law associative law distributive law

sample

$$A=\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right]$$

$$B=\left[\begin{array}{cc}1& -2\\ 2& -4\end{array}\right]$$

乘積

$$\begin{gathered} A=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right] \\ B=\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right] \\ A\ast B=\left[\begin{array}{cc}a\ast 1+b\ast 3& a\ast 2+b\ast 4\\ c\ast 1+d\ast 3& c\ast 2+d\ast 4\end{array}\right] \\ A=\left[\begin{array}{cc}2& 3\\ 1& -5\end{array}\right]B=\left[\begin{array}{ccc}4& 3& 6\\ 1& -2& 3\end{array}\right] \\ A\ast B=\left[\begin{array}{ccc}2\ast 4+3\ast 1& 2\ast 3+3\ast -2& 2\ast 6+3\ast 3\\ 1\ast 4+-5\ast 1& 1\ast 3+-5\ast -2& 1\ast 6+-5\ast 3\end{array}\right]=\left[\begin{array}{ccc}11& 0& 21\\ -1& 13& -9\end{array}\right] \\ \underset{[n\times m]}{A}\ast \underset{[m\times s]}{B}=\underset{[n\times s]}{C} \end{gathered}$$

反矩陣

$$\begin{gathered} A=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right] \\ a\ast d-b\ast c=0thennotinverable \\ A\ast A^{-1}=I=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right] \\ {A}^{-1}=\frac{1}{\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|}\ast \left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right] \\ \text{high level matrix} \\ \left[\begin{array}{cc}A& I\end{array}\right]=\left[\begin{array}{cc}A\ast A^{-1}& I\ast A^{-1}\end{array}\right]=\left[\begin{array}{cc}I& A^{-1}\end{array}\right] \\ \left[\begin{array}{ccccccc}1& 0& 0& |& 1& 0& 0\\ 1& 1& 0& |& 0& 1& 0\\ 1& 1& 1& |& 0& 0& 1\end{array}\right]=\left[\begin{array}{ccccccc}1& 0& 0& |& 1& 0& 0\\ 0& 1& 0& |& -1& 1& 0\\ 0& 0& 1& |& 0& -1& 1\end{array}\right] \\ \left[\begin{array}{ccccccc}1& 0& 0& |& 1& 0& 0\\ 1& 1& 0& |& 0& 1& 0\\ 1& 1& 1& |& 0& 0& 1\end{array}\right]=\left[\begin{array}{ccccccc}1& 0& 0& |& 1& 0& 0\\ 0& 1& 0& |& -1& 1& 0\\ 0& 0& 1& |& 0& -1& 1\end{array}\right] \end{gathered}$$

identity matrix

$$I=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$$

transpose matrix

$$\begin{gathered} A=\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right] \\ {A}^T=\left[\begin{array}{cc}1& 3\\ 2& 4\end{array}\right](A^{-1}{)}^T=(A^T{)}^{-1} \end{gathered}$$

inner change (change row)

$$\left[\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\end{array}\right]==\left[\begin{array}{cc}5& 6\\ 3& 4\\ 1& 2\end{array}\right]$$

math to matrix

$$\{\begin{array}{llccc}1\ast x_1& +& 2\ast x_2& +& 3\ast x_3=5\\ 2\ast x_1& +& 3\ast x_2& +& 4\ast x_3=7\end{array}=\left[\begin{array}{cccc}1& 2& 3& 5\\ 2& 3& 4& 7\end{array}\right]$$