跳转至

非正则语言

英文: Non-regular languages.

Pumping 引理

对于任意的正则语言 \(A\), 如果存在 \(p\) 使得 \(s \in A\)\(|s| > p\), 则 \(s = xyz\), 其中:

  • \(xy^iz \in A \text{ for all } i \geq 0\): 其中 \(y^i = \underbrace{yy \dots y}_{i}\), \(y\) 是相连的重复子串, 且 \(y\) 可能不存在.
  • \(y \neq \varepsilon\): \(y\) 不是空字符串.
  • \(|xy| \leq p\): \(y\) 在位置 \(p\)\(p\) 之前结束.

换句话说, \(s\) 会呈现某种 \(xyy \dots yz\) 的模式.

根据鸽巢原理(Pigeonhole Principle), DFA 在读取 \(s\) 的过程中, 至少会到达某个状态 \(q_j\) 两次. 如下图所示:


\[ B = \{ w \mid w \text{ 有着相同数量的 0 和 1} \} \]
\[ D = \{ 0^k1^k \mid k \geq 0 \} \\ s = 0^p1^p \in D \]

\(s\) 无法被分割为满足 Pumping 引理中三个条件的 \(xyz\).

评论