Lemme de pompage pour CFG

Lemme

Si L est un langage sans contexte, il y a une longueur de pompage p telle que toute chaîne w ∈ L de longueur ≥ p peut être écrit comme w = uvxyz, où vy ≠ ε, |vxy| ≤ p, et pour tous i ≥ 0, uvⁱxyⁱz ∈ L.

Applications du lemme de pompage

Le lemme de pompage est utilisé pour vérifier si une grammaire est sans contexte ou non. Prenons un exemple et montrons comment il est vérifié.

Problème

Découvrez si la langue L = {xⁿyⁿzⁿ | n ≥ 1} est sans contexte ou non.

Solution

Laisser Lest sans contexte. Ensuite,L doit satisfaire le lemme de pompage.

Au début, choisissez un numéro ndu lemme de pompage. Ensuite, prenez z comme 0 ⁿ 1 ⁿ 2 ⁿ .

Pause z dans uvwxy, où

|vwx| ≤ n and vx ≠ ε.

Par conséquent vwxne peut pas impliquer à la fois des 0 et des 2, puisque le dernier 0 et les 2 premiers sont séparés d'au moins (n ​​+ 1) positions. Il y a deux cas -

Case 1 - vwxn'a pas de 2. ensuitevxn'a que des 0 et des 1. ensuiteuwy, qui devrait être dans L, a n 2s, mais moins de n 0s ou 1s.

Case 2 - vwx n'a pas de 0.

Ici, la contradiction se produit.

Par conséquent, L n'est pas un langage sans contexte.