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