Skip to content

1 正则语言

Language ComputationModel
Regular Finite automata
Context-Free Pushdown automata
Non Context-Free Turing Machine

预备知识

[[../离散数学/2.Basic Structures#|2.Basic Structures]]

Diagonization Principle

Cantor Diagonalization Argument.

\(D=\{a|a \in A \wedge (a,a)\notin R\},R_a={b|b\in A \wedge (a,b)\in R}\)

\(\forall a \in A, D\neq R_a\)

证明: 对A中的每个元素c

  • 若\(c\in D\), \((c,c)\notin R, c\notin R_c\) 所以D和R_c不等
  • 若\(c \notin D\) \((c,c)\in R, c \in R_c\)

语言

  • 字母表(alphabet): 有限 的符号集合 \(\Sigma\)

  • 字符串(串)(string): 字母表中符号的组成的 有限序列

    • 连接: \(w_1w_2\) 空串\(e,\forall w,we=ew=w\)

    • \(\Sigma^*\) : 字母表上所有字符串的集合，包括空串\(e\)

定理: 如果\(\Sigma\) 是finate alphabet, 那么\(\Sigma^*\)是countable ininite的

证明: 用字典序排序,构造双射 \(f:\mathbb{N}\to \Sigma^*\) 如0,1,01,10,11,000....

但是前提是每个字符串的长度是有限的。否则类似无限循环小数，\(\mathbb{R}\)是不可数的

  • 语言(language): 字符串的集合。 \(\Sigma^*\)的子集。

Example

  • Any language over any alphabet is countable
  • How many languages over a non-empty alphabet? Uncountable: \(|2^{\Sigma^*}|=|\mathbb{R}|\)

语言的运算

Concat

\[ L_1L_2=\{w_1w_2|w_1\in L_1,w_2\in L_2\} \]

Warning

\(\boxed{L\emptyset=\emptyset}\)
因为找不到上面式子中对应的w2，所以最后结果为空 注意区分\(\emptyset\), \(e\)(空串) ${e}$(空串组成的语言)

Kleene Star

  • \(L^i\): \(L^0=\{e\},L^{i+1}=LL^i\)

\(L^*=\bigcup_{k\geq 0} L^k,L^+=\bigcup_{k\geq 1}L^k\)

Warning

  • 存在L使得\(e\in L^+\) 只要\(e\in L\)即可,那
  • \(\boxed{\emptyset^*=\{e\},\emptyset^+=\emptyset}\)
  • \(\set{e}^*=\set{e}^+=\set{e}\)
  • \(L^+=LL^*\) 因为\(LL^i=L^{i+1}\)
  • \((L^*)^*=L^*\)

正则表达式

Finite representation: 用\(\cup\), \(\circ\) \(^*\)(闭包) 和\(\Sigma\)

正则表达式(Regular expression): all strings over the alphabet \(\Sigma \cup \{(,),\cup,*\}\) (用一个字符串去表示一个语言)

正则表达式的递归定义:

正则语言(Regular Language): 能用正则表达式表示的语言。

  • 在\(\cup,\circ,*\) 下封闭.

\(L=\{a^nb^n|n \geq 0\}\) 不是正则语言 (无法表示a,b个数相等)

\(a^*(ba^*)^*=\{a,b\}^*\)

DFA

自动机和语言

\(M=(K,\Sigma,\delta,s,F)\)

  • K是状态集合
  • \(s\in K\)是起始状态(只有1个)
  • \(F\subseteq K\) 是终止状态集合
  • \(\delta\) 是转移 函数 \(K\times \Sigma \to K\)

自动机对应的语言 \(L(M)=\{M \text{ accepts } w,w \in \Sigma^*\}\)

  • Every DFA accepts one and only one language.

configuration

A configuration of a finite automaton 𝑴 tells the current state and the inputs to be read in the future.

当前状态, 和接下来要匹配的字符串。

image-20240930085115747

yields

若\(w=aw',a\in\Sigma,\delta(q,a)=q'\) 则\((q,w)\vdash (q',w')\) (\vdash)

image-20240930085231825

NFA

\(M=(K,\Sigma,\delta,s,F)\)

\(\delta\) 不是函数 是\(K\times(\Sigma\cup e)\times K\)的子集

  • 同一个状态和字符，转移到的状态可以不一样
  • 可以用空串来转移

NFA转DFA

  • 显然每个DFA都是一个NFA
  • 任给一个 NFA, 都存在与其等价的 DFA (两个自动机等价当且仅当\(L(M_1)=L(M_2)\))

NFA \(M=(K,\Sigma,\delta,s,F)\) 转换为DFA \(M'=(K',\Sigma',\delta',s',F')\)，且\(L(M)=L(M')\)

Warning

定义\(E(q)\) 为M中所有可以从q通过空串转移到的状态。\(\{p\in K|(q,e) (p,e)\}\)

  1. \(K'=2^K\)
  2. \(\Sigma=\Sigma'\)
  3. \(s'=E(s)\)

  4. \(F'=\{Q|Q \subseteq K,Q\cap F \neq \emptyset\}\)

  5. 对于任意集合\(Q\subseteq K\)(注意是子集,不是元素), \(a\in\ \Sigma\)

\[\delta'(Q,a)=\bigcup \{E(p)|q \in Q,(q,a,p)\in \delta\}\]

证明:

关键的引理 \(\((q,w)\vdash^*_M (p,e) \Leftrightarrow (E(q),w)\vdash_{M'}^* (P,e), p \in P\)\) 这样可证明等价性

\(\(w \in L(M)\Leftrightarrow (s,w)\vdash_M^*(f,e) , f\text{是final state}\)\) 根据引理变成

\[(E(s),w) \vdash_{M'}^* (Q,e), * \]

引理的证明: 按照w的长度归纳

当\(w=e\), 左到右: \((q,e) \vdash_{M}^* (p,e) \Rightarrow p \in E(q)\) (E的定义) 令\(P=E(q)\) 即可。 右到左:

当\(|w|=k+1\) 设\(w=va,a \in \Sigma\) 那么有

\(\((q,w) \vdash_M^* (r_1,a) \vdash_M (r_2,e) \vdash_{M'}^*(p,e)\)\) （根据NFA接受字符串的过程)

第一步等价于v转移后变成空串，归纳|v|=k时成立 那么 \((E(q),v)\vdash_{M'}^* (R_1,e),r_1\in R_1\)

第二步根据NFA转移函数的定义,必定存在\((r_1,a,r_2)\in \delta\). 再根据NFA转DFA的构造(上面的第5条), 因为Q是任意集合,所以可以取\(Q=R_1,q=r_1\) 则 \(E(r_2)\subseteq \delta'(R_1,a)\)

第三步 \((r_2,e)\vdash_{M}^* (p,e)\) 根据E的定义 \(p\in E(r_2)\) 根据第二步有 \(p\in \delta'(R_1,a)\), 即 \((R_1,a) \vdash_{M}^* (P,e),p\in P\)

正则语言与自动机

\(L\) is regular iff \(L=L(M)\) for some DFA \(M\)

正则表达式转自动机

考虑正则表达式的定义。起始状态显然可以用FA来表达。证明FA在这三个操作下是封闭的

Union

\(A,B\) 是正则语言，那么 \(A \cup B\) 是正则语言

Warning

Infinite unions of regular language may not be regular!!!! 比如\(\{a^nb^n,n\geq 0\}=\{ab\}\cup\{aabb\} \dots\)

Kleene Star

原理：用NFA。创建一个新的初始状态(该状态也是结束状态)，通过e-转移到A的起始状态。再将MA的结束状态用e连回MA的起始状态

  • \(A^*\) 包括空串， 但同时又不能让 MA​ 的初始状态变为接受状态

Concatenation

原理：用e-转移，把MA结束状态连到MB的起始状态

Complement

把MA的结束状态和非结束状态翻转。 \(F'=K-F\)

Intersection

跟Union类似，但是终止状态用and

\[F={(q_A,q_B),q_A\in F_A \wedge q_B \in F_B}\]

自动机转正则表达式

思路: 把边"缩起来", 边上从字符变成正则表达式。自环是Kleene star, 两条不同路径是\(\cup\).

首先加两个状态\(s_G,f_G\) (新建一个起点，再把F连到一个终点)

Pumping Theorem

证明语言是正则的是容易的

证明语言不是正则的?

Warning

Pumping Theorem: 令L为一个正则语言，则存在整数\(p\geq 1\),使得对于所有长度不小于p的字符串\(w\), 都可以把\(w\)分解成三部分\(w=xyz\),满足:

(1) \(\forall k \geq 0,xy^kz\in L\). (2) \(|y|\geq 1\)(即不为空串)
(3)\(|xy|\leq p\) (x和y长度之和不超过p)

证明不是正则语言: 需要证明\(\forall n\), 存在字符串\(w \in L,|w|\geq n\). 对任意一种\(w=xyz\)的拆分方式, 都不可能满足上面3个条件(一般用\(\exists i\), \(xy^iz\notin L\) 来构造)

\(L=\set{a^nb^n}\) 不是正则语言

那么\(0^n1^n\in L=xyz\) , 且满足 \(|y|\geq 1,|xy|\leq n\) 显然有\(y=0^t(t \geq 1)\) 再令\(k=0\),则 \(xy^kz=0^{n-t}1^n \notin L\)

推论\(\set{w\in \set{a,b}^*且a,b数量相等}\) 不是正则语言。 因为\(L=\set{a^nb^n}\) 是它的子集，由正则语言关于\(\cap\) 的封闭性反证法即可

\(L=a^n, n\text{ is prime}\)

\(L_0\)是正则语言

  • \(L=\{w^R,w\in L_0\}\) 是
  • \(L=\{ww^R,w\in L_0\}\) 不是
  • \(L=\{ww,w\in L_0\}\) 不是

【计算理论】计算理论总结 ( 泵引理 Pumping 证明 ) ★★-CSDN博客

【编译原理】泵引理_泵引理证明不是正则语言-CSDN博客

Comments