⌘ '

raccourcis clavier

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^{*}$ :

\overline{L} = \Sigma^{*} - L

associative:

\begin{align*} (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{align*}

commutative:

\begin{align*} A \cup B &= B \cup A \\ A \cap B &= B \cap A \end{align*}

null set

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

$A \cup \emptyset = A$ and $A \emptyset = \emptyset A = \emptyset$

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

Set union and intersection are distributive over set concatenation

\begin{align*} 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{align*}

Set concatenation distributes over union

\begin{align*} A(B \cup C) &= AB \cup AC \\\ (A \cup B)C &= AC \cup BC \end{align*}

DFA

definition

\Sigma^{*}: \text{set of all strings based off }\Sigma

\begin{align*} \text{DFA}\quad M &= (Q, \Sigma, \delta, s, F) \\\ Q &: \text{finite set of states} \\\ \Sigma &: \text{finite alphabet} \\\ \delta &: Q \times \Sigma \rightarrow Q \rightarrow \delta: Q \times \Sigma \rightarrow Q \\\ s &: \text{start state},\quad s\in{Q} \\\ F &: \text{set of final states},\quad F\subseteq{Q} \\\ \end{align*}

examples

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

\begin{align*} Q &= \{s_1, s_2, s_3, s_4\} \\\ s &= 1 \\\ F &= \{s_4\} \\\ \end{align*}

Transition function:

\begin{align*} \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{align*}

representation:

stateDiagram-v2
    direction LR
    classDef accepting fill:#4CAF50,stroke:#333,stroke-width:2px
    classDef start fill:#FFD700,stroke:#333,stroke-width:2px

    s1: s1
    s2: s2
    s3: s3
    s4: s4

    [*] --> s1
    s1 --> s1: b
    s1 --> s2: a

    s2 --> s2: b
    s2 --> s3: a

    s3 --> s3: b
    s3 --> s4: a

    s4 --> s4: a,b

    class s4 accepting
    class s1 start

if in final string then accept, otherwise reject the string

Let $\delta : Q \times \Sigma \rightarrow Q$ , thus $\hat{\delta} : Q \times \Sigma^{*} \rightarrow Q$

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

regularity

Important

$\begin{align*} \hat{\delta}(q, \epsilon) &= q \\\ \hat{\delta}(q, xa) &= \delta(\hat{\delta}(q, x), a) \end{align*}$

Important

a subset $A \subset \Sigma^{*}$ 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 = \epsilon \}$ , 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\} \rightarrow \delta(q_{0}, x) = 0 \iff \#x \equiv 0 \space mod \space 3$ , $\delta(q_{0}, x) = q_{1} \iff \#x \equiv 1 \space mod \space 3$ , $\delta(q_{0}, x) = q_{2} \iff \#x \equiv 2 \space mod \space 3$

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) \quad 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)) \space \forall x \in \Sigma^*$

Complement set: $Q - F \in Q$

Trivial machine $\mathcal{L}(M_{1}) = \{\}$ , $\mathcal{L}(M_{2}) = \Sigma^*$ , $\mathcal{L}(M_{3})=\{ \epsilon \}$

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^{*}: \text{set of all strings based off }\Sigma

\begin{align*} \text{NFA}\quad M &= (Q, \Sigma, \Delta, S, F) \\\ Q &: \text{finite set of states} \\\ \Sigma &: \text{finite alphabet} \\\ \Delta &: Q \times \Sigma \rightarrow P(Q) \\\ S &: \text{Start states},\quad S \subseteq Q \\\ F &: \text{Final states},\quad F \subseteq Q \\\ \end{align*}

transition function

$\hat{\Delta}: P(Q) \times \Sigma^* \rightarrow P(Q)$

\begin{align*} \hat{\Delta}(A, a) &= \bigcup_{p \in \hat{\Delta}(A, \varepsilon)} \Delta(p, a) \\\ & \\\ &= \bigcup_{p \in A} \Delta(p, a). \end{align*}

subset construction

acceptance

$N$ accepts $x \in \Sigma^*$ if
$\hat{\Delta}(s, x) \cap F \neq \emptyset$

Define $L(N) = \{ x \in \Sigma^* \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^* \land 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{align*} 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 \neq \emptyset \} \end{align*}

Lemma 6.3

For any $A \subseteq Q_N \land x \in \Sigma^*$
$\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(\epsilon) = \{\epsilon\}$
$L(\emptyset) = \emptyset$
$L(\#) = \Sigma$ : matched by any symbols
$L(@) = \Sigma^*$ : matched by any string

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

redundancy

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

if $\alpha$ and $\beta$ are patterns, then so are $\alpha + \beta, \alpha \cap \beta, \alpha^*, \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) \land z \in L(\beta)\}$

$L(\alpha^*) = L(\alpha)^0 \cup L(\alpha)^1 \cup \dots = L(\alpha)^*$

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

Theorem 7.1

$\Sigma^* = L(\#^*) = L(@)$

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

Finite set: $\{x_{1},x_{2},\dots,x_m\} = L(x_{1}+x_{2}+\dots+x_m)$

Theorem 9

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

quotient automata

also known as DFA state minimization

definition

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

Define

M / \approx \space = (Q', \Sigma, \delta', [s], F')

where (13.1)

\begin{align*} Q' &= Q / \approx \\\ \delta'([p], a) &= [\delta(p, a)] \\\ s' &= [s] \\\ F' &= \{ [p] \mid p \in F \} \end{align*}

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 \iff [p] \in F'$

Lemma 13.7

$\forall x \in \Sigma^*, \hat{\delta'}([p], x) = [\hat{\delta}(p, x)]$

Theorem 13.8

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

algorithm

Table of all pairs $\{p, q\}$

Mark all pairs $\{p, q\}$ if $p \in F \land q \notin F \lor q \in F \land p \notin F$

If there exists unmarked pair $\{p, q\}$ , such that $\{ \delta(p, a), \delta(q, a) \}$ is marked, then mark $\{p, q\}$

$p \approx q \iff \{p, q\}$ is not marked

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^{*}$ :

\overline{L} = \Sigma^{*} - L

associative:

\begin{align*} (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{align*}

commutative:

\begin{align*} A \cup B &= B \cup A \\ A \cap B &= B \cap A \end{align*}

null set

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

$A \cup \emptyset = A$ and $A \emptyset = \emptyset A = \emptyset$

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

Set union and intersection are distributive over set concatenation

\begin{align*} 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{align*}

Set concatenation distributes over union

\begin{align*} A(B \cup C) &= AB \cup AC \\\ (A \cup B)C &= AC \cup BC \end{align*}

DFA

url: thoughts/.../DFA
description: DFA
definition
$\Sigma^{*}: \text{set of all strings based off }\Sigma$ $\begin{align*} \text{DFA}\quad M &= (Q, \Sigma, \delta, s, F) \\\ Q &: \text{finite set of states} \\\ \Sigma &: \text{finite alphabet} \\\ \delta &: Q \times \Sigma \rightarrow Q \rightarrow \delta: Q \times \Sigma \rightarrow Q \\\ s &: \text{start state},\quad s\in{Q} \\\ F &: \text{set of final states},\quad F\subseteq{Q} \\\ \end{align*}$
examples

Ex: $\Sigma = \{a, b\}$ . Creates a DFA $M$ that accepts all strings that contains at least three a’s.
$\begin{align*} Q &= \{s_1, s_2, s_3, s_4\} \\\ s &= 1 \\\ F &= \{s_4\} \\\ \end{align*}$
Transition function:
$\begin{align*} \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{align*}$
representation:
stateDiagram-v2
    direction LR
    classDef accepting fill:#4CAF50,stroke:#333,stroke-width:2px
    classDef start fill:#FFD700,stroke:#333,stroke-width:2px

    s1: s1
    s2: s2
    s3: s3
    s4: s4

    [*] --> s1
    s1 --> s1: b
    s1 --> s2: a

    s2 --> s2: b
    s2 --> s3: a

    s3 --> s3: b
    s3 --> s4: a

    s4 --> s4: a,b

    class s4 accepting
    class s1 start
if in final string then accept, otherwise reject the string

Lien vers l'original

Let $\delta : Q \times \Sigma \rightarrow Q$ , thus $\hat{\delta} : Q \times \Sigma^{*} \rightarrow Q$

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

regularity

Important

$\begin{align*} \hat{\delta}(q, \epsilon) &= q \\\ \hat{\delta}(q, xa) &= \delta(\hat{\delta}(q, x), a) \end{align*}$

Important

a subset $A \subset \Sigma^{*}$ 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 = \epsilon \}$ , 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.

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) \quad 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)) \space \forall x \in \Sigma^*$

Complement set: $Q - F \in Q$

Trivial machine $\mathcal{L}(M_{1}) = \{\}$ , $\mathcal{L}(M_{2}) = \Sigma^*$ , $\mathcal{L}(M_{3})=\{ \epsilon \}$

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

url: thoughts/.../NFA
description: NFA
definition
$\Sigma^{*}: \text{set of all strings based off }\Sigma$ $\begin{align*} \text{NFA}\quad M &= (Q, \Sigma, \Delta, S, F) \\\ Q &: \text{finite set of states} \\\ \Sigma &: \text{finite alphabet} \\\ \Delta &: Q \times \Sigma \rightarrow P(Q) \\\ S &: \text{Start states},\quad S \subseteq Q \\\ F &: \text{Final states},\quad F \subseteq Q \\\ \end{align*}$ Lien vers l'original

transition function

$\hat{\Delta}: P(Q) \times \Sigma^* \rightarrow P(Q)$

\begin{align*} \hat{\Delta}(A, a) &= \bigcup_{p \in \hat{\Delta}(A, \varepsilon)} \Delta(p, a) \\\ & \\\ &= \bigcup_{p \in A} \Delta(p, a). \end{align*}

subset construction

acceptance

$N$ accepts $x \in \Sigma^*$ if
$\hat{\Delta}(s, x) \cap F \neq \emptyset$

Define $L(N) = \{ x \in \Sigma^* \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^* \land 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{align*} 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 \neq \emptyset \} \end{align*}

Lemma 6.3

For any $A \subseteq Q_N \land x \in \Sigma^*$
$\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(\epsilon) = \{\epsilon\}$
$L(\emptyset) = \emptyset$
$L(\#) = \Sigma$ : matched by any symbols
$L(@) = \Sigma^*$ : matched by any string

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

redundancy

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

if $\alpha$ and $\beta$ are patterns, then so are $\alpha + \beta, \alpha \cap \beta, \alpha^*, \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) \land z \in L(\beta)\}$

$L(\alpha^*) = L(\alpha)^0 \cup L(\alpha)^1 \cup \dots = L(\alpha)^*$

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

Theorem 7.1

$\Sigma^* = L(\#^*) = L(@)$

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

Finite set: $\{x_{1},x_{2},\dots,x_m\} = L(x_{1}+x_{2}+\dots+x_m)$

Theorem 9

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

quotient automata

also known as DFA state minimization

definition

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

Define

M / \approx \space = (Q', \Sigma, \delta', [s], F')

where (13.1)

\begin{align*} Q' &= Q / \approx \\\ \delta'([p], a) &= [\delta(p, a)] \\\ s' &= [s] \\\ F' &= \{ [p] \mid p \in F \} \end{align*}

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 \iff [p] \in F'$

Lemma 13.7

$\forall x \in \Sigma^*, \hat{\delta'}([p], x) = [\hat{\delta}(p, x)]$

Theorem 13.8

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

algorithm

Table of all pairs $\{p, q\}$

Mark all pairs $\{p, q\}$ if $p \in F \land q \notin F \lor q \in F \land p \notin F$

If there exists unmarked pair $\{p, q\}$ , such that $\{ \delta(p, a), \delta(q, a) \}$ is marked, then mark $\{p, q\}$

$p \approx q \iff \{p, q\}$ is not marked

Automata

Étiquette

publié à

modifié à

durée

source

Set theory

DFA

definition

examples

regularity

examples

product construction

NFA

definition

subset construction

regex

quotient automata

Vous pourriez aimer ce qui suit