泵引理

维基百科,自由的百科全书
跳转至: 导航搜索

可计算性理论中的形式语言理论中,泵引理声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸,如果在这个语言中任何足够长的字符串可以分解成片段,其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理


两个最重要例子是正则语言的泵引理上下文无关语言的泵引理Ogden引理是另一种更强的上下文无关语言的泵引理。

这些引理可以用来确定特定语言在给定语言类中。但是它们不能被用来确定一个语言在给定类中,因为满足引理是类成员关系的必要条件,但不是充分条件。

泵引理是1961年由 Y. Bar-HillelM. PerlesE. Shamir 首次发表的[1]

正则語言的泵引理[编辑]

定义[编辑]

假设L \subseteq \Sigma^*正则语言,存在字符串w \in L\left| w \right| \ge n(n为泵长度,可理解为正则语言等效的DFA的状态个数),如果可以将w写成w = xyz的形式时,以下说法成立:

  1. \left| xy \right| \le n
  2. \left| y \right| \ge 1
  3. \forall k \ge 0:xy^kz \in L

泵引理也可以写成以下的形式:……w \notin L…… \rightarrow ……xy^kz \notin L……

正确性的证明[编辑]

  • 因为L是正则语言,所以存在一个与之等价的确定有限状态自动机
  • 假设n是这个确定有限状态自动机中状态的数量,
  • 假设w \in L\left| w \right| \ge n
  • 在这个自动机读入w的前n个字符后一定有一个状态达到过两次,
  • 也就是说对于其中一种w的分解方式w=xyz有\delta^* \left( s,x \right)=\delta^* \left( s,xy \right)
  • 因此对于所有的k \ge 0都有\delta^*(s,xyz) \in L \leftrightarrow \delta^*(s,xy^kz) \in L

應用[编辑]

通过泵引理可以用反證法證明L不是正则語言。证明的时候需要注意以下几点:

  1. 假设要证明的语言为正则语言
  2. n是未知的
  3. w可以在满足w \in L\left| w \right| \ge n的条件下自由选择
  4. x,y,z也是未知的
  5. 找到一个k,使得xy^kz \notin L,也就是说和泵引理的第三条矛盾

一个证明L不是正则语言的例子

  • 证明L_{01} = \{0^n1^n|n\geq1\}不是正则语言
    • 假设L_{01}是正则语言,令n為泵引理常數
    • 选择w = 0^n1^n \in L,则\left| w \right| \ge n
    • 于是存在x,y,z使得w=xyz满足条件\left| xy \right| \le n\left| y \right| \ge 1\forall k \ge 0:xy^kz \in L_{01}
    • 因为\left| xy \right| \le n且,\left| y \right| \ge 1所以y中不包含1但最少有一个0
    • 当k=0的时候,xy^kz = xy^0z = xz,xz中1的数量比0多,所以xz \notin L_{01}
    • 与泵引理的第三条矛盾,因此L_{01}不是正则语言

普遍化的泵引理[2][编辑]

并不是所有满足泵引理的语言都是正则语言。L = \{ a^mb^nc^n | m,n \ge 1 \} \cup \{b^mc^n|m,n \ge 0 \}就是这样的一个例子,它虽然满足泵引理,但并不是正则语言。Jeffrey Jaffe发展出了一个普遍化的泵引理,使它可以证明一个语言是正则语言。它的描述如下:

  • 一个语言L \subseteq \Sigma^*是正则语言,当且仅当存在一个自然数n \in \mathbb{N},使得任意字符串w\in \Sigma^*可以通过至少一种方式被写成w = xyz的形式时,以下说法成立:
      1. \left| xy \right| \le n
      2. \left| y \right| \ge 1
      3. \forall k \ge 0\forall v \in \Sigma^* :xyzv \in L \leftrightarrow xy^kzv \in L

一个可行的用于判断一个语言是否为正则语言的方法,可以参见迈希尔-尼罗德定理。一般来说证明一个语言是正则的,可以通过对该语言构造一个有限状态机正则表达式来实现。

上下文無關語言的泵引理[编辑]

定義[编辑]

L上下文無關語言,則存在一常數 n > 0 使得語言 L 中每個字串 w 的長度 |w| ≧ n,而當 w = uvxyz 時:

  1. |vxy| ≦ n
  2. |vy| ≧ 1,且
  3. 對所有的 k ≧ 0,字串 uvkxykz 屬於 L

應用[编辑]

透過泵引理反證法證明 L 不是上下文無關語言

  • L = \{a^nb^nc^n|n \geq 1 \}L = \{a^ib^ic^i|i \geq 0\}L = \{a^ib^ic^i|i \geq 2\},換句話說,L 就是包含 a^*b^*c^* 所有字串且 abc 三者數目相同的語言。
    • n泵引理常數,w = a^nb^nc^n 屬於 Lw = uvxyz,而 |vxy| ≤ n,|vy| ≥ 1,則 vxy 不可能同時包含 ac
      1. vxy 不包含 a 時,vy 只可能包含 bc,則 uxz 包含 na 及不到 n 個的 bc,使得 uxz 不屬於 L
      2. vxy 不包含 c 時,uxz 會包含 nc 及不到 n 個的 ab,使得 uxz 不屬於 L
    • 因此,無論是上述何種狀況,L 都不會是上下文無關語言
  • L = \{a^ib^j|j = i^2\}
    • n泵引理常數,w = a^nb^{n^2}w = uvxyz,而 |vxy| ≤ n,|vy| ≥ 1
      1. vxy 只包含 a,則 uxz 會包含不到 nan^2b,不屬於 L
      2. vxy 只包含 b,則 uxz 會包含 na 及不到 n^2b,不屬於 L
      3. vxy 裡有 a 也有 b
        1. vy 包含 abuv^2xy^2z 不在 \{a^ib^j\} 裡;
        2. v 只包含 la,且 y 只包含 mbuv^{1+k}xy^{1+k}z 會包含 n + lkan^2 + mkb,由於兩者都是線性成長,不可能永遠滿足 \{a^ib^j|j = i^2\} 的條件,不屬於 L
    • 因此,無論是上述何種狀況,L 都不會是上下文無關語言
  • L = \{ww|w \in \{0,1\}^* \}
    • n泵引理常數,w = 0^n1^n0^n1^n 屬於 Lw = uvxyz,而 |vxy| ≤ n,|vy| ≥ 1,則 |uxz|≥ 3n。(未完)
  • L = \{x^iy^jz^k|i \ne j \; and \; j \ne k \}
  • L = \{b^na^2nb^n|n \geq 0\}
  • L = \{a^nb^mc^m|n,m \geq 0\}

引用[编辑]

  1. ^ Y. Bar-Hillel, M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung 14 (1961) pp. 143-172.
  2. ^ Jeffery Jaffe: A necessary and sufficient pumping lemma for regular languages
  • Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X.  Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.