跳转至

2 Regular Language and Automata

2.1 Deterministic Finite Automata

DFA 的状态图

A deterministic finite automata (DFA) is a quintuple \((K, \Sigma, \delta, s, F)\), where

  • \(K\) is a finite set of states
  • \(\Sigma\) is an alphabet
  • \(s \in K\) is the initial state
  • \(F \subseteq K\) is the set of final states
  • \(\delta : K \times \Sigma \to K\) is the transition function

Transition function will determine unique next state based on current input and state. 给定状态和输入确定性地得到下一个状态

Example

A configuration of a DFA \((𝐾, Σ, 𝛿, 𝑠, 𝐹)\) is in \(𝐾 × \Sigma^*\)，给出当前状态以及之后会读入的字符串

Binary relation \(\vdash_M\) between two configurations of \(M\)

\[ (q, w) \vdash_M (q', w') \iff \exists a \in \Sigma, \text{ such that } w = aw' \text{ and } \delta(q, a) = q' \]
  • \((q, w) \vdash_M (q', w')\) if the automaton \(M\) can pass from the configuration \((q, w)\) to \((q', w')\) in one step.

\(\vdash_M^*\) is the reflexive, transitive closure of \(\vdash_M\)，也就是说 \(\vdash_M\) 是一步，然后 \(\vdash_M^*\) 是零步或者多步。

A string \(w \in \Sigma^*\) is said to be accepted by \(M\) iff there is a state \(q \in F\) such that \((s, w) \vdash_M^* (q, \varepsilon)\).

\(L(M)\) is the language accepted by \(M\) and is the set of all strings accepted by \(M\)

2.2 Nondeterministic Finite Automata

A nondeterministic finite automata (NFA) is a quintuple \((K, \Sigma, \delta, s, F)\), where

  • \(K\) is a finite set of states
  • \(\Sigma\) is an alphabet
  • \(s \in K\) is the initial state
  • \(F \subseteq K\) is the set of final states
  • \(\Delta\): transition relation, is the subset of \(K \times (\Sigma \cup \{\varepsilon\}) \times K\)

在 DFA 中 \(\delta\) 是一个函数，但是在 NFA中 \(\Delta\) 是一个关系，其他类似 \(\vdash_M\) 和 \(\vdash_M^*\) 以及 \(L(M)\) 的定义都是类似的

NFA 虽然看起来比 DFA 强大，但其二者实际上是等价的

  • \(\forall\) NFA \(M\), \(\exists\) DFA \(M'\), s.t. \(L(M) = L(M')\)
  • \(\forall\) DFA \(M\), \(\exists\) NFA \(M'\), s.t. \(L(M) = L(M')\)

两者等价性的一个直观理解：虽然 NFA 看似不确定，实则是在状态的幂集中（有限）挑选一个确定的组合

NFA 转 DFA 主要思路

  • NFA 接收一个字符，会有多个转移方案，所有可达的下一状态合在一起的集合构成 DFA 的一个状态
  • 即 DFA 的状态是 NFA 的状态的幂集，结束状态是包含 NFA 的结束状态的 DFA 状态
  • \(\varepsilon\)-transition 也要考虑，且不算在字符里

NFA \(M = (K, \Sigma, \Delta, s, F)\) 转为 DFA \(M' = (K', \Sigma, \delta, s', F')\)

  • \(K' = 2^K = \{Q : Q \subseteq K\}\)
  • \(F' = \{Q \in K' : Q \cap F \neq \emptyset\}\)
  • \(s' = E(s)\)
  • 定义 \(\forall q \in K\), \(E(q) = \{p \in K : (q, \varepsilon) \vdash_M^* (p, \varepsilon)\}\)
  • 即 \(E(q)\) 是 \(q\) 可以通过 \(\varepsilon\)-transition 到达的状态集合
  • \(\delta\): \(\forall Q \in K', \forall a \in \Sigma\)
\[ \delta(Q, a) = \bigcup_{q \in Q} \bigcup_{p: (q,a,p) \in \Delta} E(p) \]
步骤 内容
1️⃣ 写出 NFA 的五元组 \((K,Σ,Δ,s,F)\)
2️⃣ DFA 的状态来自 \(2^K\) 的子集（实际只需构造可达状态）
3️⃣ 初始状态：\(s'=E(s)\)（若有 ε-转移则取闭包，否则就是 \({s}\)）
4️⃣ 对每个未处理的状态集合 \(Q\)，对每个输入符号 \(a∈Σ\)：计算 \(δ(Q,a)=⋃_{q∈Q}Δ(q,a)\)，如果有 \(ε\)-转移，还要取 \(ε\)-closure
5️⃣ 如果新状态未出现过，加入待处理队列
6️⃣ 所有包含原接受状态的集合，都是新 DFA 的接受状态：\(F′={Q∈K′∣Q∩F≠∅}\)
7️⃣ 输出 DFA \((K',Σ,δ,s',F')\)

2.3 FA & Regular Expression

Theorem：A Language \(𝐿\) is regular iff it is accepted by a finite automata \(𝑀\), i.e., \(𝐿 = 𝐿(M)\)

正则语言的定义

By definition, \(𝐿\) is regular iff there is a regular expression \(𝑟 ∈ R\) that represents \(L\)

上述定理应该如何证明？

  • 给定一个正则表达式，根据其递归结构，逐层构造对应的 FA。
  • 给定 FA，构造正则表达式

前者的构造比较容易，如下构造：

  1. \(ε\)：空串 → 构造只有一个状态、自环或直接接受的状态
  2. \(a∈Σ\)：单个字符 → 构造两个状态之间的一条边
  3. \(r_1+r_2\)：并集 → 并联两个 FA
  4. \(r_1⋅r_2\)：连接 → 串联两个 FA
  5. \(r^*\)：闭包 → 添加循环回路

对于后者，我们先引入一个概念就是 generalized finite automaton 广义有限自动机，主要特性如下

  • 只有一个接受状态
  • 字母表扩展为正则表达式集合（每条边不仅可以为字母表，也可以为正则表达式
  • 初始状态和最终状态没有反向连接

如何从一个 DFA 或者 NFA 转化为广义有限自动机？

  • 加两个状态，一个进入状态 \(q_{n-1}\)，一个结束状态 \(q_n\)
  • \(q_{n-1}\) 指向所有原先初始状态，所有结束状态指向 \(q_n\)

然后只需要在广义有限自动机的基础上利用正则表达式展示边来消除中间的变量即可

正则语言在布尔运算以及连接 (·)、Kleene星号 (*) 等运算下都是封闭的，只需要从 FA 的角度去思考即可，构造相应的 DFA

2.4 Languages that are and are not regular

如何判断一个语言是否正则？

  • 被一个 FA 所接受
  • 由一个正则表达式所表示
  • 通过闭包的性质得到（如两个正则语言的并）

Example

Let \(\Sigma = \{0,1,\dots,9\}\). Let \(L = \{ w \in \Sigma^* \mid w\) is the decimal representation of a nonnegative integer (without redundant leading 0's) divisible by both 2 and 3} \(\}\).Show that \(L\) is regular.

三个正则表达式的交

对于如何证明一个语言是非正则的，一个很好用的定理是泵定理

Theorem: (Pumping Lemma for Regular Languages)

Let \(L\) be a regular language. Then there exists an integer \(n \geq 1\) such that for any string \(w \in L\) with \(|w| \geq n\), we can write \(w = xyz\) satisfying the following conditions:

  • \(y \neq \varepsilon\) (i.e., \(y\) is non-empty)
  • \(|xy| \leq n\)
  • For every integer \(i \geq 0\), the string \(xy^iz \in L\)

直观地表达一下就是由于状态是有限的，那么无限的正则语言肯定会在某些状态下产生重复，这样就可以无限重复下去（就像一个泵一样）。

注意这个定理主要用于证明某个语言不是正则的，思路是这样的，如果某个语言是正则的，那么这个语言满足泵定理，从而去找这个泵，如果不管怎么样找这个泵都能找到相应的 \(i\), 使得重复 \(i\) 次泵之后得到的字符串并属于这个语言，那么这个语言就不是正则的了

Example

Review

  1. Say whether each of the following languages is regular or not regular? Prove your answers, where \(\{a,b\}^+= \{a,b\}^*◦ \{a,b \}\).

(a) \(L_1 = \{wtw|w,t \in \{a,b\}^+\}\)

(b) \(L_2 = \{wtw|w,t \in \{a,b\}^*\}\)

Answer

(a) 【正则语言判断，泵定理的应用】假设 \(L_1\) 是正则的，令 n 是一个足够大的数，使得泵引理（pumping lemma）保证存在。取字符串 \(w =a^nbaa^nb\)，此时泵定理成立。让 \(w = xyz\)，其中 \(|xy|<n\) 并且 \(y \ne e\)，那么 \(y = a^i,i>0\) 这样 \(xy^2z = a^{n+i}baa^nb\notin L_1\) ，矛盾，从而 \(L_1\) 不是正则的

(b) 注意这里 \(w\) 可以为 \(e\)，所以 \(L_2 = \{a,b\}^*\)

  1. If \(𝐿_1 ∘ 𝐿_2\) is regular, then either \(𝐿_1\) or \(𝐿_2\) is regular.
Answer

False，回忆一下连接的概念。这个题的反例如下构造，找一个非正则语言 \(A\)，然后 \(L_1\) 为 \(A\cup\{e\}\)，\(L_2\) 为 \(\overline{A}\cup\{e\}\)，这样 \(𝐿_1 ∘ 𝐿_2\) 为 \(\Sigma^*\)

  1. Every regular language has a regular proper subset.
Answer

False, 考虑空集

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！