Lemme de pompage pour les grammaires régulières

Théorème

Soit L une langue régulière. Alors il existe une constante‘c’ tel que pour chaque chaîne w dans L -

|w| ≥ c

On peut casser w en trois cordes, w = xyz, tel que -

  • | y | > 0
  • | xy | ≤ c
  • Pour tout k ≥ 0, la chaîne xy k z est également dans L.

Applications du lemme de pompage

Le lemme de pompage doit être appliqué pour montrer que certaines langues ne sont pas régulières. Il ne doit jamais être utilisé pour montrer qu'une langue est régulière.

  • Si L est régulier, il satisfait le lemme de pompage.

  • Si L ne satisfait pas le lemme de pompage, il est non régulier.

Méthode pour prouver qu'une langue L n'est pas régulière

  • Au début, nous devons supposer que L est régulier.

  • Donc, le lemme de pompage devrait tenir pendant L.

  • Utilisez le lemme de pompage pour obtenir une contradiction -

    • Sélectionner w tel que |w| ≥ c

    • Sélectionner y tel que |y| ≥ 1

    • Sélectionner x tel que |xy| ≤ c

    • Attribuez la chaîne restante à z.

    • Sélectionner k de sorte que la chaîne résultante ne soit pas L.

Hence L is not regular.

Problem

Prouve-le L = {aibi | i ≥ 0} n'est pas régulier.

Solution -

  • Au début, nous supposons que L est régulier et n est le nombre d'états.

  • Soit w = a n b n . Ainsi | w | = 2n ≥ n.

  • En pompant le lemme, soit w = xyz, où | xy | ≤ n.

  • Soit x = a p , y = a q , et z = a r b n , où p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Ainsi | y | ≠ 0.

  • Soit k = 2. Alors xy 2 z = a p a 2q a r b n .

  • Nombre de as = (p + 2q + r) = (p + q + r) + q = n + q

  • Par conséquent, xy 2 z = a n + q b n . Puisque q ≠ 0, xy 2 z n'est pas de la forme a n b n .

  • Ainsi, xy 2 z n'est pas dans L. Donc L n'est pas régulier.