Quelle partie du théorème de la lemme de pompage pour les langues reg indique si je suis en train de pomper ou de sortir et combien de fois j'ai pompé l'entrée/sortie?

Question

Examen à venir et prof veut ces informations incluses. Je comprends comment fonctionne le lemme, mais je ne peux pas conceptualiser la façon dont le «pompage» se produit en termes d'entrée ou de sortie et combien de fois.

Answer 1

Le lemme de pompage pour les langues régulières est une condition nécessaire, mais pas suffisante, pour la régularité d'un langage formel. Si L est un langage régulier, alors il y a un nombre naturel p tel que au moins p peut être écrit s = xyz, où de toute chaîne de longueur:

• y a une longueur d'au moins un;
• xy a une longueur non supérieure à p;
• x (y^n) p est aussi dans L pour tout nombre naturel n.

Logiquement, la condition est:

1. if (L is regular) then 
2. there exists a natural number p such that 
3.  if s is in L and |s| >= p then 
4.   s = xyz 
5.   and |y| > 0 
6.   and |xy| <= p 
7.   and x(y^n)z is in L 

Sur la ligne 7, on dit que "pompés" versions de la chaîne s doit être en L. A noter que pour n = 1, nous récupérons même s ; Nous avons déjà supposé que s est dans L par l'hypothétique dans la ligne 3. Que vous «pompage» ou «pompage», et de combien, dépend de votre sélection de n.

Le lemme de pompage pour les langues régulières fonctionne par cette logique:

1. Si une langue est régulière, il y a un minimum DFA pour elle.
2. Si un DFA minimal pour la langue a des états p, toute chaîne dans le langage de longueur p ou plus doit avoir obligé le DFA à visiter plusieurs états plusieurs fois (principe du pigeonhole).
3. Si le DFA a visité un état plusieurs fois, il existe un cycle dans le DFA et cette chaîne a provoqué le DFA pour le traverser.
4. Si cette chaîne, qui a provoqué la DFA pour faire défiler un certain nombre de fois, est en L, il y a d'autres chaînes qui parcourent le cycle plusieurs fois ou moins de fois que doit également être en L.

Compte tenu de cette logique:

1. p = nombre hypothétique d'états dans un DFA minimal l
2. x = la partie de la chaîne d'entrée avant un certain cycle a été exécuté
3. y = la partie de la chaîne d'entrée représentant un cycliste exécuté e
4. z = la partie de la chaîne d'entrée après un cycle a été exécuté

Par exemple, considérons cette DFA minimale:

 0,1  0  /---\ 
--->(q0)--->(q1)--->(q2)<--/ 0,1 
    ^  | 
     \------/ 
      1 

La chaîne 0100 est en L. p = 3 et | 0100 | = 4, donc le lemme de pompage doit tenir. Nos seuls choix pour x, y et z sont x = 0, y = 10 et z = 0. Le lemme de pompage prétend que nous pouvons nous débarrasser de y ou y ajouter n'importe quel nombre de multiples et obtenir une autre chaîne dans L. Nous voyons que cela fonctionne parce que y est simplement la boucle de q1 à q0; on peut l'ignorer (n = 0) ou on peut le répéter (n> 1).