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, uvixyiz ∈ 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 = {xnynzn | 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 n 1 n 2 n .
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.