Automata

Book: pdf

Q1: T/F, if F explain why. Q4: regular expression, 5 separate q Q2/Q3: DFAs and NFAs

• Product construction: $\cap$ $\cup$ of DFAs
• Subset construction: NFA to DFA
• Quotient construction: State minimization

Set theory

Complement in ${\Sigma }^{\ast }$:

$$\overline{L}={\Sigma }^{\ast }-L$$

associative:

$$\begin{array}{rl}(A\cup B)\cup C& =A\cup (B\cup C),\\ (A\cap B)\cap C& =A\cap (B\cap C),\\ (AB)C& =A(BC).\end{array}$$

commutative:

$$\begin{array}{rl}A\cup B& =B\cup A\\ A\cap B& =B\cap A\end{array}$$

null set

null set $\varnothing$ is the identity for $\cup$ and annihilator for set concatenation

$A\cup \varnothing =A$ and $A\varnothing =\varnothing A=\varnothing$

set $\{ϵ\}$ is an identity for set concatenation $\{ϵ\}A=A\{ϵ\}=A$

Set union and intersection are distributive over set concatenation

$$\begin{array}{rl}A\cup (B\cap C)& =(A\cup B)\cap (A\cup C)\\ A\cap (B\cup C)& =(A\cap B)\cup (A\cap C)\end{array}$$

Set concatenation distributes over union

$$\begin{array}{rl}A(B\cup C)& =AB\cup AC\\ (A\cup B)C& =AC\cup BC\end{array}$$

DFA

definition

$${\Sigma }^{\ast }:\text{set of all strings based off }\Sigma$$ $$\begin{array}{rl}\text{DFA}M& =(Q,\Sigma ,\delta ,s,F)\\ Q& :\text{finite set of states}\\ \Sigma & :\text{finite alphabet}\\ \delta & :Q\times \Sigma \to Q\to \delta :Q\times \Sigma \to Q\\ s& :\text{start state},s\in Q\\ F& :\text{set of final states},F\subseteq Q\\ & \end{array}$$

examples

Ex: $\Sigma =\{a,b\}$. Creates a DFA $M$ that accepts all strings that contains at least three a’s.

$$\begin{array}{rl}Q& =\{s_1,s_2,s_3,s_4\}\\ s& =1\\ F& =\{s_4\}\\ & \end{array}$$

Transition function:

$$\begin{array}{r}\delta (1,a)=s_2\\ \delta (1,b)=s_1\\ \delta (2,a)=s_3\\ \delta (2,b)=s_2\\ \delta (3,a)=s_4\\ \delta (3,b)=s_3\\ \delta (4,a)=\delta (4,b)=s_4\\ \end{array}$$

representation:

stateDiagram-v2
  direction LR

  [*] --> 1
  1 --> 1 : b
  1 --> 2 : a
  2 --> 2 : b
  2 --> 3 : a
  3 --> 3 : b
  3 --> 4 : a
  4 --> 4 : a, b
  4 --> [*]

if in final string then accept, otherwise reject the string

Lien vers l'original

Let $\delta :Q\times \Sigma \to Q$, thus $\hat{\delta }:Q\times {\Sigma }^{\ast }\to Q$

$\delta (q,c)\to p$ therefore $\hat{\delta }(q,w)\to p$

regularity

Important

$$\begin{array}{rl}\hat{\delta }(q,ϵ)& =q\\ \hat{\delta }(q,xa)& =\delta (\hat{\delta }(q,x),a)\end{array}$$

Important

a subset $A\subset {\Sigma }^{\ast }$ is regular if and only if there exists a DFA $M$ such that $\mathcal{L}(M)=L$

Important

All finite languages are regular, but not all regular languages are finite

examples

Show $L$ is regular where $L=\{x\mid x\%3=0\cup x=ϵ\}$, with $\Sigma =\{0,1\}$

Three states, $q_0,q_1,q_2$, where $q_0$ denotes the string mod 3 is 0, $q_1$ denotes the string mod 3 is 1, and $q_2$ denotes the string mod 3 is 2.

$\forall x\in \{0,1\}\to \delta (q_0,x)=0⟺\#x\equiv 0mod3$, $\delta (q_0,x)=q_1⟺\#x\equiv 1mod3$, $\delta (q_0,x)=q_2⟺\#x\equiv 2mod3$

stateDiagram-v2
  direction LR

  [*] --> q0
  q0 --> q1 : 1
  q0 --> q0 : 0
  q1 --> q2 : 0
  q1 --> q0 : 1
  q2 --> q1 : 0
  q2 --> q2 : 1
  q0 --> [*]

---

product construction

Assume that A, B are regular, there are automata

$$M_1=(Q_1,\Sigma ,{\delta }_1,s_1,F_1)M_2=(Q_2,\Sigma ,{\delta }_2,s_2,F_2)$$

Thus

$$M_3=(Q_3,\Sigma ,{\delta }_3,s_3,F_3)$$

where $Q_3=Q_1\times Q_2$, $s_3=(s_1,s_2)$, $F_3=F_1\times F_2$, and ${\delta }_3((p,q),x)=({\delta }_1(p,x),{\delta }_2(q,x))$

with $L(M_1)=A$ and $L(M_2)=B$, then $A\cap B$ is regular.

Lemma 4.1

$${\delta }_3((p,q),x)=({\delta }_1(p,x),{\delta }_2(q,x))\forall x\in {\Sigma }^{\ast }$$

Complement set: $Q-F\in Q$

Trivial machine $\mathcal{L}(M_1)=\{\}$, $\mathcal{L}(M_2)={\Sigma }^{\ast }$, $\mathcal{L}(M_3)=\{ϵ\}$

De Morgan laws

$$A\cup B=\overline{\overline{A}\cap \overline{B}}$$

Theorem 4.2

$$L(M_3)=L(M_1)\cap L(M_2)$$

$\overline{L}$ is regular

$L_1\cap L_2$ is regular

$L_1\cup L_2$ is regular

---

NFA

definition

$${\Sigma }^{\ast }:\text{set of all strings based off }\Sigma$$ $$\begin{array}{rl}\text{NFA}M& =(Q,\Sigma ,\Delta ,S,F)\\ Q& :\text{finite set of states}\\ \Sigma & :\text{finite alphabet}\\ \Delta & :Q\times \Sigma \to P(Q)\\ S& :\text{Start states},S\subseteq Q\\ F& :\text{Final states},F\subseteq Q\\ & \end{array}$$ Lien vers l'original

transition function

$\hat{\Delta }:P(Q)\times {\Sigma }^{\ast }\to P(Q)$

$$\begin{array}{rl}\hat{\Delta }(A,a)& =\bigcup _{p\in \hat{\Delta }(A,\epsilon )}\Delta (p,a)\\ & \\ & =\bigcup _{p\in A}\Delta (p,a).\end{array}$$

subset construction

acceptance

$N$ accepts $x\in {\Sigma }^{\ast }$ if

$$\hat{\Delta }(s,x)\cap F\ne \varnothing$$

Define $L(N)=\{x\in {\Sigma }^{\ast }\mid N\text{ accepts }x\}$

Theorem 4.3

Every DFA $(Q,\Sigma ,\delta ,s,F)$ is equvalent to an NFA $(Q,\Sigma ,\Delta ,\{s\},F)$ where $\Delta (p,a)=\{\delta (p,a)\}$

Lemma 6.1

For any $x,y\in {\Sigma }^{\ast }\wedge A\subseteq Q$,

$$\hat{\Delta }(s,xy)=\hat{\Delta }(\hat{\Delta }(s,x),y)$$

Lemma 6.2

$\hat{\Delta }$ commutes with set union:

$$\hat{\Delta }(\bigcup _i{A}_i,x)=\bigcup _i\hat{\Delta }(A_i,x)$$

Let $N=(Q_N,\Sigma ,{\Delta }_N,S_N,F_N)$ be arbitrary NFA. Let M be DFA $M=(Q_M,\Sigma ,{\delta }_M,s_M,F_M)$ where:

$$\begin{array}{rl}{Q}_M& =P(Q_N)\\ {\delta }_M(A,a)& ={\hat{\Delta }}_N(A,a)\\ s_M& =S_N\\ F_M& =\{A\in Q_N\mid A\cap F_N\ne \varnothing \}\end{array}$$

Lemma 6.3

For any $A\subseteq Q_N\wedge x\in {\Sigma }^{\ast }$

$${\hat{\delta }}_M(A,x)={\hat{\Delta }}_N(A,x)$$

Theorem 6.4

The automata M and N accept the same sets.

regex

atomic patterns are:

• $L(a)=\{a\}$
• $L(ϵ)=\{ϵ\}$
• $L(\varnothing )=\varnothing$
• $L(\#)=\Sigma$: matched by any symbols
• $L(@)={\Sigma }^{\ast }$: matched by any string

compound patterns are formed by combining binary operators and unary operators.

redundancy

$a^{+}\equiv a{a}^{\ast }$, $\alpha \cap \beta =\overline{\overline{\alpha }+\overline{\beta }}$

if $\alpha$ and $\beta$ are patterns, then so are $\alpha +\beta ,\alpha \cap \beta ,{\alpha }^{\ast },{\alpha }^{+},\overline{\alpha },\alpha \beta$

The following holds for x matches:

$L(\alpha +\beta )=L(\alpha )\cup L(\beta )$

$L(\alpha \cap \beta )=L(\alpha )\cap L(\beta )$

$L(\alpha \beta )=L(\alpha )L(\beta )=\{yz\mid y\in L(\alpha )\wedge z\in L(\beta )\}$

$L({\alpha }^{\ast })=L(\alpha {)}^0\cup L(\alpha {)}^1\cup \cdots =L(\alpha {)}^{\ast }$

$L({\alpha }^{+})=L(\alpha {)}^{+}$

Theorem 7.1

${\Sigma }^{\ast }=L({\#}^{\ast })=L(@)$

Singleton set $\{x\}=L(x)$

Finite set: $\{x_1,x_2,\dots ,x_m\}=L(x_1+x_2+\cdots +x_m)$

Theorem 9

$$\begin{array}{cccl}\alpha +(\beta +\gamma )& \equiv & (\alpha +\beta )+\gamma & (9.1)\\ \alpha +\beta & \equiv & \beta +\alpha & (9.2)\\ \alpha +\varphi & \equiv & \alpha & (9.3)\\ \alpha +\alpha & \equiv & \alpha & (9.4)\\ \alpha (\beta \gamma )& \equiv & (\alpha \beta )\gamma & (9.5)\\ ϵ\alpha & \equiv & \alpha ϵ\equiv \alpha & (9.6)\\ \alpha (\beta +\gamma )& \equiv & \alpha \beta +\alpha \gamma & (9.7)\\ (\alpha +\beta )\gamma & \equiv & \alpha \gamma +\beta \gamma & (9.8)\\ \varphi \alpha & \equiv & \alpha \varphi \equiv \varphi & (9.9)\\ ϵ+{\alpha }^{\ast }& \equiv & {\alpha }^{\ast }& (9.10)\\ ϵ+{\alpha }^{\ast }& \equiv & {\alpha }^{\ast }& (9.11)\\ \beta +\alpha \gamma \le \gamma & \Rightarrow & {\alpha }^{\ast }\beta \le \gamma & (9.12)\\ \beta +\gamma \alpha \le \gamma & \Rightarrow & \beta {\alpha }^{\ast }\le \gamma & (9.13)\\ (\alpha \beta {)}^{\ast }& \equiv & \alpha (\beta \alpha {)}^{\ast }& (9.14)\\ ({\alpha }^{\ast }\beta {)}^{\ast }{\alpha }^{\ast }& \equiv & (\alpha +\beta {)}^{\ast }& (9.15)\\ {\alpha }^{\ast }(\beta {\alpha }^{\ast }{)}^{\ast }& \equiv & (\alpha +\beta {)}^{\ast }& (9.16)\\ (ϵ+\alpha {)}^{\ast }& \equiv & {\alpha }^{\ast }& (9.17)\\ \alpha {\alpha }^{\ast }& \equiv & {\alpha }^{\ast }\alpha & (9.18)\end{array}$$

quotient automata

also known as DFA state minimization

definition

$$p\approx q\equiv [p]=[q]$$

Define

$$M/\approx =(Q^{\prime },\Sigma ,{\delta }^{\prime },[s],F^{\prime })$$

where (13.1)

$$\begin{array}{rl}{Q}^{\prime }& =Q/\approx \\ {\delta }^{\prime }([p],a)& =[\delta (p,a)]\\ s^{\prime }& =[s]\\ F^{\prime }& =\{[p]\mid p\in F\}\end{array}$$

Lemma 13.5

If $p\approx q$, then $\delta (p,a)\approx \delta (q,a)$ equivalently, if $[p]=[q]$, then $[\delta (p,a)]=[\delta (q,a)]$

Lemma 13.6

$p\in F⟺[p]\in F^{\prime }$

Lemma 13.7

$$\forall x\in {\Sigma }^{\ast },\widehat{{\delta }^{\prime }}([p],x)=[\hat{\delta }(p,x)]$$

Theorem 13.8

$L(M/\approx )=L(M)$

algorithm

1. Table of all pairs $\{p,q\}$
2. Mark all pairs $\{p,q\}$ if $p\in F\wedge q\notin F\vee q\in F\wedge p\notin F$
3. If there exists unmarked pair $\{p,q\}$, such that $\{\delta (p,a),\delta (q,a)\}$ is marked, then mark $\{p,q\}$
4. $p\approx q⟺\{p,q\}$ is not marked