Automata Theory 简明教程

Pumping Lemma For Regular Grammars

Theorem

设 L 是正则语言。那么存在常量 ‘c’ 使得对于 L 中的每个字符串 w −

Let L be a regular language. Then there exists a constant ‘c’ such that for every string w in L −

|w| ≥ c

|w| ≥ c

我们可以把 w 分成三个字符串 w = xyz ，使得 −

We can break w into three strings, w = xyz, such that −

  1. |y| > 0

  2. |xy| ≤ c

  3. For all k ≥ 0, the string xykz is also in L.

Applications of Pumping Lemma

抽取引理用于证明某些语言不是正则的。它不应该被用来证明语言是正则的。

Pumping Lemma is to be applied to show that certain languages are not regular. It should never be used to show a language is regular.

  1. If L is regular, it satisfies Pumping Lemma.

  2. If L does not satisfy Pumping Lemma, it is non-regular.

Method to prove that a language L is not regular

  1. At first, we have to assume that L is regular.

  2. So, the pumping lemma should hold for L.

  3. Use the pumping lemma to obtain a contradiction − Select w such that |w| ≥ c Select y such that |y| ≥ 1 Select x such that |xy| ≤ c Assign the remaining string to z. Select k such that the resulting string is not in L.

Hence L is not regular.

Hence L is not regular.

Problem

Problem

证明 L = {aibi | i ≥ 0} 不是正则的。

Prove that L = {aibi | i ≥ 0} is not regular.

Solution −

Solution −

  1. At first, we assume that L is regular and n is the number of states.

  2. Let w = anbn. Thus |w| = 2n ≥ n.

  3. By pumping lemma, let w = xyz, where |xy| ≤ n.

  4. Let x = ap, y = aq, and z = arbn, where p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Thus |y| ≠ 0.

  5. Let k = 2. Then xy2z = apa2qarbn.

  6. Number of as = (p + 2q + r) = (p + q + r) + q = n + q

  7. Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.

  8. Thus, xy2z is not in L. Hence L is not regular.