Finite Automata

Finite Automata and Regular Languages

Definitions

DFA: Deterministic Finite Automaton

a DFA is a 5-tuple \((Q, \Sigma, \delta, q_0, F)\) where

  • \(Q\) is a finite set called the states.
  • \(\Sigma\) is a finite set called the alphabet.
  • \(\delta: Q \times \Sigma \to Q\) is the transition function.
  • \(q_0 \in Q\) is the start state.
  • \(F \subseteq Q\) is the set of accept states.

In a DFA, for each state q and input symbol a, there is exactly one state p such that δ(q, a) = p.

graph LR
    S0((S0)); S1((S1)); S2((S2));

    S0 -- 0 --> S2;
    S2 -- 0 --> S1;
    S2 -- 1 --> S0;
    S0 -- 1 --> S1;
    S1 -- 0 --> S0;
    S1 -- 1 --> S1;

    style S0 fill:#fff,stroke:#333,stroke-width:2px
    style S1 fill:#ccf,stroke:#333,stroke-width:4px

Computation of a DFA:

Let \(M = (Q, \Sigma, \delta, q_0, F)\) be a DFA and let \(w = w_1 w_2 ... w_n\) be a string with \(w_i \in \Sigma\) for \(\forall i \in [n]\).

Define: M accepts w if there exists a sequence of states \(r_0, r_1, ..., r_n\) such that:

  1. \(r_0 = q_0\),
  2. for each \(i\) (\(0 \leq i < n\)), \(r_{i+1} = \delta(r_i, w_{i+1})\),
  3. \(r_n \in F\).

Function/Semantics/Language of a DFA:

The set of strings accepted by \(M\) is called the language of \(M\), denoted by \(L(M)\).

A language is called regular if some DFA recognizes it.

\[ A = L(M) = \{ w | M \text{ accepts } w \} \]

Discussions

  1. a certain M -> a certain language A; a certain A -> multiple constructions of M

  2. The definition of regular language infers that the corresponding DFA must can judge whether a string belongs to the language or not in finite time.

Exercises

  1. Design a DFA over the alphabet \(\Sigma = \{0, 1\}\) so that it accepts all strings that have same number of substrings “01” and “10”.

graph LR
    S0((S0)); S1((S1)); S2((S2));

    S0 -- 0 --> S1;
    S0 -- 1 --> S2;
    S1 -- 0 --> S1;
    S1 -- 1 --> S0;
    S2 -- 0 --> S0;
    S2 -- 1 --> S2;

    %% style S0 fill:#fff,stroke:#333,stroke-width:2px
    style S0 fill:#ccf,stroke:#333,stroke-width:4px

  1. Design a DFA over the alphabet \(\Sigma = \{0, 1\}\) so that it accepts all strings that contain the substring “101”.

graph LR
    S0((S0)); S1((S1)); S2((S2)); S3((S3));

    S0 -- 0 --> S0;
    S0 -- 1 --> S1;
    S1 -- 0 --> S2;
    S1 -- 1 --> S0;
    S2 -- 0 --> S0;
    S2 -- 1 --> S3;
    S3 -- 0, 1 --> S3;

    style S0 fill:#fff,stroke:#333,stroke-width:2px
    style S3 fill:#ccf,stroke:#333,stroke-width:4px

Non-determinism Automata

Definitions

NFA: Non-deterministic Finite Automaton

a 5-tuple \((Q, \Sigma, \delta, q_0, F)\) where

  • \(Q\) is a finite set called the states.
  • \(\Sigma\) is a finite set called the alphabet.
  • \(\delta: Q \times \Sigma_\varepsilon \to P(Q)\) is the transition function, where \(\Sigma_\varepsilon = \Sigma \cup \{\varepsilon\}\) and \(P(Q)\) is the power set of Q.
  • \(q_0 \in Q\) is the start state.
  • \(F \subseteq Q\) is the set of accept states.

In an NFA, there can be multiple possible next states for each state q and input symbol a, including the empty string ε. Empty string \(\varepsilon\) means that the state can transition to another state without consuming any input symbol.

graph LR
    S0((S0)); S1((S1)); S2((S2)); S3((S3));

    S2 -- 0 --> S1;
    S1 -- 1 --> S1;

    S3 -- 0 --> S1;
    S3 -- 1 --> S2;

    S0 -- 0 --> S2;
    S2 -- 1 --> S0;

    S0 -- 1 --> S1;
    S1 -- 0 --> S0;

    S0 -.-> S3;
    S2 -.-> S3;

    style S0 fill:#fff,stroke:#333,stroke-width:2px
    style S1 fill:#ccf,stroke:#333,stroke-width:4px

Let N is a NFA, then N accepts a string w if there exists a sequence of states \(r_0 , r_1, ..., r_n\) such that:

  • \(r_0 = q_0\)
  • \(\forall i \in [0, n)\), \(r_{i+1} \in \delta(r_i, w_{i+1})\). (Here \(=\) is replaced by \(\in\))
  • \(r_n \in F\)

Equivalence of DFA and NFA

Theorem: Every NFA has an equivalent DFA.

Construct a DFA D from a NFA N

Let NFA be \[ N=(Q,\Sigma,\delta,q_0,F), \] where

  • \(Q\): set of states
  • \(\Sigma\): input alphabet
  • \(q_0\in Q\): initial state
  • \(F\subseteq Q\): set of accept states
  • \(\delta:Q\times(\Sigma\cup\{\varepsilon\})\to 2^Q\): transition function (allowing \(\varepsilon\)-transitions)

Goal: Construct DFA \[ D=(Q_D,\Sigma,\delta_D,S_0,F_D) \] such that \(L(D)=L(N)\).

  1. Define \(\varepsilon\)-closure (epsilon-closure)

    For any set \(S\subseteq Q\), define \[ \varepsilon\text{-closure}(S)=\{q\in Q \mid \exists s\in S,\ s \xRightarrow{\varepsilon^*} q\}. \]

    Meaning: all states reachable from set \(S\) by following any number of \(\varepsilon\) edges (including the states themselves).

  2. DFA State Space

    Each DFA state is a set of NFA states: \[ Q_D \subseteq 2^Q. \]

    Typically, only generate those set-states reachable from the initial state (to avoid enumerating the entire \(2^Q\)).

  3. DFA Initial State

    \[ S_0=\varepsilon\text{-closure}(\{q_0\}). \]

  4. DFA Transition Function (move + closure)

    First define the move operation: for \(S\subseteq Q\) and input symbol \(a\in\Sigma\), \[ \text{move}(S,a)=\bigcup_{q\in S}\delta(q,a). \]

    Then the DFA transition is \[ \delta_D(S,a)=\varepsilon\text{-closure}(\text{move}(S,a)). \]

  5. Generate All Reachable DFA States (Queue / BFS)

    Algorithm:

    • Initialize: \(Q_D=\{S_0\}\), queue \(\text{Queue}=[S_0]\)
    • While queue is not empty:
      • Dequeue a set-state \(S\)
      • For each \(a\in\Sigma\):
      • Compute \(T=\delta_D(S,a)\)
      • If \(T\notin Q_D\), add \(T\) to \(Q_D\) and enqueue it
    • When queue is empty, \(Q_D\) contains all reachable set-states.

  6. DFA Accept States

    \[ F_D=\{S\in Q_D \mid S\cap F\neq\varnothing\}. \]

    Explanation: a set-state is accepting if it contains at least one NFA accept state.

  7. Add Dead State for Total Transition Function

    If there exists \(S\in Q_D\) and \(a\in\Sigma\) such that \[ \delta_D(S,a)=\varnothing, \] we can add \(\varnothing\) as a dead state to \(Q_D\), and define \[ \delta_D(\varnothing,a)=\varnothing\quad \forall a\in\Sigma, \] so that the DFA has a defined transition for every input symbol.

Corollary: A language is regular iif some NFA recognizes it.

Proof of Equivalence

  1. \(L(N) \subseteq L(D)\)

    Let \(w \in L(N)\). Then there exists a sequence of states \(r_0, r_1, ..., r_n\) such that:

    • \(r_0 = q_0\)
    • for each \(i\) (\(0 \leq i < n\)), \(r_{i+1} \in \delta(r_i, w_{i+1})\)
    • \(r_n \in F\)

    We will show that the DFA \(D\) constructed from \(N\) will also accept \(w\).

    The DFA \(D\) simulates all possible transitions of the NFA \(N\). At each step, it keeps track of all possible states that \(N\) could be in after reading each symbol of \(w\). Since \(w\) is accepted by \(N\), there exists a sequence of states leading to an accept state in \(N\). Therefore, \(D\) will also reach an accept state after processing \(w\).

  2. \(L(D) \subseteq L(N)\)

    Let \(w \in L(D)\). Then the DFA \(D\) reaches an accept state after processing \(w\).

    Since \(D\) simulates all possible transitions of \(N\), there must exist a sequence of states in \(N\) that leads to an accept state after reading \(w\). Therefore, \(w\) is also accepted by \(N\).

    严格证明需要对输入长度 \(|w|\) 做数学归纳。

    Base case: \(|w| = 0\)，即 \(w = \varepsilon\)。\(D\) 停在 \(\{q_0\} \cup E(\{q_0\})\)（包含 \(\varepsilon\)-闭包），与 \(N\) 在 \(\varepsilon\) 上可达的状态集一致。

    Inductive step: 假设对长度 \(\leq k\) 的输入，\(D\) 在读完后的状态集恰好等于 \(N\) 可能处于的所有状态的集合。对输入 \(w = xa\)（\(|x| = k\)），\(D\) 在读完 \(x\) 后的状态为 \(R\)（由归纳假设，等于 \(N\) 在 \(x\) 上可达状态集）。然后 \(D\) 读 \(a\)：\(D\) 转移到 \(\bigcup_{r \in R} E(\delta(r, a))\)，恰好等于 \(N\) 在 \(xa\) 上可达的状态集。

    因此 \(D\) 接受 \(w\) \(\iff\) \(D\) 最终状态集中包含接受状态 \(\iff\) \(N\) 有某条接受路径。

Regular Expressions

Relation between regular expressions and regular languages

Theorem: A language is regular iff some regular expression recognizes it.

(\(\Rightarrow\)) Regular expression \(\to\) Regular language：对正则表达式的结构做归纳。

  • Base: \(a\), \(\varepsilon\), \(\emptyset\) 各对应一个简单的 NFA。
  • Inductive step: \(R_1 \cup R_2\), \(R_1 \circ R_2\), \(R_1^*\) 分别用 NFA 的并、连接、星号构造。

(\(\Leftarrow\)) DFA \(\to\) Regular expression：使用 GNFA（Generalized NFA） 方法。

  1. 将 DFA 转换为 GNFA：添加新的起始状态和唯一接受状态，边上标注正则表达式。
  2. 逐步消除中间状态：每消除一个状态 \(q_{rip}\)，对于每一对剩余状态 \((q_i, q_j)\)，更新边上的正则表达式： \[R'(q_i, q_j) = R(q_i, q_j) \cup R(q_i, q_{rip}) \circ R(q_{rip}, q_{rip})^* \circ R(q_{rip}, q_j)\]
  3. 当只剩起始状态和接受状态时，两者之间的边标注即为所求正则表达式。

Q.E.D.

Closure under the regular operators

Regular Operators:

  • Union: \(A \cup B = \{w | w \in A \text{ or } w \in B\}\)
  • Concatenation: \(A \odot B = \{ xy | x \in A \land y \in B \}\)
  • Kleene Star: \(A^* = \{x_1 x_2 ... x_k | k \geq 0 \land xi ∈ A\}\)

Theorem: If A and B are regular languages, then so are \(A \cup B\), \(A \odot B\), and \(A^*\).

Proof: Construct NFAs for each operation.

  1. \(A \cup B\)

    Let \(N_A = (Q_A, \Sigma, \delta_A, q_{0A}, F_A)\) and \(N_B = (Q_B, \Sigma, \delta_B, q_{0B}, F_B)\) be NFAs recognizing A and B, respectively.

    Construct a new NFA \(N = (Q, \Sigma, \delta, q_0, F)\) where:

    • \(Q = Q_A \cup Q_B \cup \{q_0\}\) (a new start state)
    • \(\delta(q_0, \varepsilon) = \{q_{0A}, q_{0B}\}\)
    • \(\delta(q, a) = \delta_A(q, a)\) for \(q \in Q_A\) and \(a \in \Sigma\)
    • \(\delta(q, a) = \delta_B(q, a)\) for \(q \in Q_B\) and \(a \in \Sigma\)
    • \(F = F_A \cup F_B\)

  2. \(A \odot B\)

    Let \(N_A = (Q_A, \Sigma, \delta_A, q_{0A}, F_A)\) and \(N_B = (Q_B, \Sigma, \delta_B, q_{0B}, F_B)\) be NFAs recognizing A and B, respectively.

    Construct a new NFA \(N = (Q, \Sigma, \delta, q_0, F)\) where:

    • \(Q = Q_A \cup Q_B\)
    • \(\delta(q, a) = \delta_A(q, a)\) for \(q \in Q_A\) and \(a \in \Sigma\)
    • \(\delta(q, a) = \delta_B(q, a)\) for \(q \in Q_B\) and \(a \in \Sigma\)
    • For each accept state \(f \in F_A\), add an ε-transition to the start state of \(N_B\): \(\delta(f, \varepsilon) = \{q_{0B}\}\)
    • \(q_0 = q_{0A}\)
    • \(F = F_B\)

  3. \(A^*\)

    Let \(N_A = (Q_A, \Sigma, \delta_A, q_{0A}, F_A)\) be an NFA recognizing A.

    Construct a new NFA \(N = (Q, \Sigma, \delta, q_0, F)\) where:

    • \(Q = Q_A \cup \{q_0\}\) (a new start state)
    • \(\delta(q_0, \varepsilon) = \{q_{0A}\}\)
    • \(\delta(q, a) = \delta_A(q, a)\) for \(q \in Q_A\) and \(a \in \Sigma\)
    • For each accept state \(f \in F_A\), add an ε-transition back to the start state of \(N_A\): \(\delta(f, \varepsilon) = \{q_{0A}\}\)
    • \(q_0\) is also an accept state: \(F = F_A \cup \{q_0\}\)

Corollary: Given \(N = (Q, \Sigma, \delta, q, F)\) the set of language recognized by N is A, then,

  • \(\overline{A} = \Sigma^\star - A\)
  • \(A \cap B\)

is closed under the regular operators.

proof:

  • w.l.o.g(without loss of generality), N is a DFA, then \(\overline{N} = (Q, \Sigma, \delta, q, Q - F)\) recognizes \(\overline{A}\).
  • \(A \cap B = \overline{\overline{A} \cup \overline{B}}\), then it is closed under the regular operators.
  • another way to prove the \(A \cap B\): (let two DFAs run in parallel)
    • let \(M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)\) and \(M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)\) be two DFAs recognizing A and B, respectively.
    • then \(M = (Q_1 \times Q_2, \Sigma, \delta, (q_1, q_2), F_1 \times F_2)\) recognizes \(A \cap B\), where \(\delta((p, q), a) = (\delta_1(p, a), \delta_2(q, a))\).

Definitions of Regular Syntax

Given alphabet \(\Sigma\), we say that \(R\) is a regular expression if \(R\) is

  1. \(a\) for some \(a \in \Sigma\),
  2. \(\varepsilon\),
  3. \(\emptyset\),
  4. \((R_1 \cup R_2)\), where \(R_1\) and \(R_2\) are regular expressions,
  5. \((R_1 \circ R_2)\), where \(R_1\) and \(R_2\) are regular expressions,
  6. \((R_1^*)\), where \(R_1\) is a regular expression.

Sometimes, we use \(R_1 R_2\) instead of \((R_1 \circ R_2)\) if no confusion arises.

Language defined by regular expression:

Regular Expression \(R\) Language \(L(R)\)
\(a\) \(\{a\}\)
\(\varepsilon\) \(\{\varepsilon\}\)
\(\emptyset\) \(\emptyset\)
\((R_1 \cup R_2)\) \(L(R_1) \cup L(R_2)\)
\((R_1 \odot R_2)\) \(L(R_1) \odot L(R_2)\)
\((R_1^\star)\) \(L(R_1)^\star\)

Examples:

  1. \(R \odot \varepsilon = R\) for any regular expression R.

  2. \(\emptyset^\star = \{\varepsilon\}\), because \(\varepsilon \in A^\star\) for any language A.

  3. \(R \odot \emptyset = \emptyset\) for any regular expression R.

  4. \((0 \cup 1)^\star\) over \(\Sigma = \{0, 1\}\) denotes the language of all binary strings.

Equivalence of Regular Expressions and Regular Languages

Theorem: A language is regular iff some regular expression describes it.

Proof:

  • if: build the NFAs; relatively easy.
  • only-if: Automata to Regular Expressions:
    • Define a path from state i to state j as a sequence of states starting with i and ending with j.
    • \(R(i, j, k) \equiv \{w | w \text{ is a string from i to j, and } \forall q_s \in w, q_s \leq k\}\)
    • so we have \(R(i, j, k) = R(i, j, k-1) \cup R(i, k, k-1) R(k, k, k-1)^\star R(k, j, k-1)\)
    • and \(L(M) = \bigcup \{ R(1, j, n) | q_j \in \mathcal{F} \}\)
    • use dynamic programming to compute \(R(i, j, n)\), by increasing k from 0 to n, we can derive the regular expression for the language of M.

Pumping Lemma for Regular Languages

If A is a regular language, then there is a number p (the pumping length) such that any string s in A with length at least p (|s| ≥ p) can be divided into three parts, s = xyz, satisfying the following conditions:

  1. for each i ≥ 0, the string \(xy^iz \in A\),
  2. \(|y| > 0\),
  3. \(|xy| \leq p\).

Attention: A regular language must satisfy the pumping lemma, but what satisfies pumping lemma does not have to be a regular language!

Proof: pigeonhole principle

Let \(M = (Q, \Sigma, \delta, q_1, F)\) be a DFA recognizing \(A\) and \(p = |Q|\). Let \(s = s_1 s_2 ... s_n\) be a string in A with \(n \geq p\). Let \(r_1, ..., r_{n+1}\) be the sequence of states that \(<\) enters while processing \(s\), i.e. \(r_{i+1} = \delta(r_i, s_i)\) for \(i \in [n]\).

Among the first \(p+1\) states in the sequence, two must be the same, say \(r_j\) and \(r_k\) with \(j < k \leq p+1\). Define

\[ x=s_1 s_2 ... s_{j-1}, \quad y=s_j s_{j+1} ... s_{k-1}, \quad z=s_k s_{k+1} ... s_n \]

Q.E.D.

1. \(L = \{0^n 1^n \mid n \geq 0\}\) is not regular.

设 \(p\) 为泵长度。取 \(s = 0^p 1^p \in L\)，\(|s| = 2p \geq p\)。

由泵引理，\(s = xyz\)，\(|xy| \leq p\)，\(|y| > 0\)。因此 \(y = 0^i\)（\(i \geq 1\)），即 \(y\) 全部由 0 组成。

取 \(i = 0\)：\(xz = 0^{p-i} 1^p\)，其中 \(p - i < p\)，故 \(xz \notin L\)。矛盾！

2. \(L = \{w \mid w \text{ has equal number of 0s and 1s}\}\) is not regular.

假设 \(L\) 是正则语言。由闭包性质，\(L \cap 0^* 1^*\) 也是正则语言。

但 \(L \cap 0^* 1^* = \{0^n 1^n \mid n \geq 0\}\)，由上面的证明知这不是正则语言。矛盾！

3. \(L = \{wtw \mid w, t \in \{0, 1\}^+\}\) is not regular.

注意：\(L\) 的补集 \(\overline{L}\) 是所有不能写成 \(wtw\)（\(|w|, |t| \geq 1\)）形式的字符串。可以证明 \(\overline{L}\) 不是正则的，从而 \(L\) 也不是正则的（正则语言对补运算封闭）。

Attention: A regular language must satisfy the pumping lemma, but what satisfies the pumping lemma does not have to be a regular language!

Language Problems concerning FA

Usual problems from formal language theory:

  • Acceptance: does a given string belong to a given language?
  • Emptiness: is a given language empty?
  • Equality: are given two languages equal?
  • Acceptance: Given a DFA (NFA) \(A\) and a string \(w\), does \(A\) accept \(w\)?
  • Emptiness: Given a DFA (NFA) \(A\), is the language \(L(A)\) empty?
  • Equality: Given two DFA (NFA) \(A\) and \(B\), is \(L(A)\) equal to \(L(B)\)?

The corresponding decision problems are all decidable.

  • Acceptance: Just run the machine \(M\) on \(w\).
  • Emptiness: Analyze the DFA \(M\). If we can not reach any accept state, then \(L(M) = \emptyset\).
  • Equality: Given two DFAs \(M_1\) and \(M_2\), we can test if \(L(M_1) = L(M_2)\) by checking if \(L(M_1) \triangle L(M_2) = \emptyset\), where \(\triangle\) denotes the symmetric difference. Since regular languages are closed under union, intersection, and complement, we have \(L(M_1) \triangle L(M_2) = (L(M_1) \cap \overline{L(M_2)}) \cup (\overline{L(M_1)} \cap L(M_2))\). We can construct a DFA for this symmetric difference and check if its language is empty using the emptiness test.