Définition du lemme de pompage (à partir du wiki)lemme de pompage pour une expression régulière très simple
Soit L un langage régulier. Alors il existe un entier p ≥ 1 ne dépendant que de L tel que chaque chaîne w dans L de longueur au moins p (p est appelée "longueur de pompage" [4]) peut s'écrire w = xyz (ie, w peut être divisé en trois sous-chaînes), répondant aux conditions suivantes:
| y | ≥ 1; | xy | ≤ p pour tout i ≥ 0, xyiz ∈ L
Supposons que je veux tester l'expression régulière 011 Comme il est expressionm régulière, il est une chaîne w pour une longueur au moins p qui satisfont w = xyz
Le nombre de cet automate est 3, p devrait être> = 3 Mais seule chaîne qui accepte cet automate est 011 Donc, je prends 011 comme w Je peux diviser 3 partie 011 = xyz mais comment puis-je casser? Je ne peux pas satisfaire | y | ≥ 1; | xy | ≤ p pour tout i ≥ 0, xyiz ∈ L
Puisqu'il n'accepte que 011 Comment puis-je pomper? Où suis-je tort
Lemme de pompage est pour les langues ordinaires et non pour les expressions. Quelle est la langue dans cette question? – sinanspd
@sinanspd: Chaque expression régulière (au sens CS) définit un langage régulier unique. Dans ce cas * L * = {"011"}. – ruakh
@ruakh ouais je pensais que le langage serait plus large car le pompage d'une langue d'une seule expression est relativement plus facile – sinanspd