Longueur de pompage minimum pour les langues régulières suivantes

Question

Quelle est la longueur de pompage minimale pour les langues suivantes?

1. Le langage vide
2. (01)*
3. 10(11*0)*0
4. 1011
5. 011 U 0*1*

Voici mes solutions. Corrigez-moi si j'ai tort, s'il-vous plait.

1. p = 0 parce que la langue n'a pas de chaînes pompables
2. p = 2 parce que 01 est la plus courte chaîne qui peut être pompée
3. p = 5 parce que 10100 est la plus courte chaîne qui peut être pompée
4. p = 0 parce que la chaîne ne peut pas être pompée
5. p = 1 car la chaîne 0 peut être pompé

Je ne suis pas sûr de mes réponses, donc toute aide est appréciée. Merci beaucoup!

Answer 1

Selon la norme Patrick87, la longueur de pompage minimale est définie comme le nombre maximal de transitions que vous pouvez effectuer dans un DFA réduit sans avoir visité deux fois un état. Le processus devient alors de convertir votre expression régulière en NFA, convertir la NFA en DFA, minimiser la DFA et compter le plus long chemin le long des bords dirigés sans visiter le même état deux fois. Pour une introduction à cette conversion et à la minimisation, voir par exemple le livre gratuit de Torben Mogensen, Basics of Compiler Design chapitres 2.6, 2.8.

Selon cette définition,

1. p = 0, car il n'y a pas de transitions dans le DFA réduit pour la langue vide.
2. p = 1. Une DFA minimisée pour (01)* a deux états, et vous ne pouvez effectuer qu'une transition sans finir à l'état initial acceptant.
3. p = 3. Un DFA minimisé pour 10(11*0)*0 aura un état qui doit être visité deux fois pour que la sous-expression (11*0)* fasse partie de la dérivation.
4. p = 4. Une DFA minimisée pour 1011 a exactement 4 arêtes et aucune récursivité.
5. p = 1. Le langage 011 est un sous-ensemble du langage 0*1*, donc 011 U 0*1* = 0*1*. Et puisque ni 0 ou 1 peuvent être pompés, on peut seulement suivre un bord non récursif.

Answer 2

Je pense que la réponse de Simon peut être un peu éteint. En fait, vous devez faire un cycle quelque part. Le lemme de pompage nécessite que le chemin emprunté pour reconnaître la corde comprenne un cycle (c'est le «y» du lemme de pompage «xyz»).Nous pouvons prendre ce cycle autant de fois que nous le voulons, ce qui pompe la corde.

1. Ceci doit être 1. La longueur de pompage minimale doit toujours être supérieure à 0, même s'il n'y a pas de chaînes dans la langue.
2. Cela devrait être 2. Si p = 1, nous ne pouvons pas pomper 01 (parce que y doit être égal à 0, et 001 n'est pas dans la langue).
3. Ceci devrait être 5.
4. Cela devrait également être 5. Si nous définissons p = 4, alors nous affirmons que "1011" est pompable (ce qui n'est pas le cas, car c'est la seule chaîne dans la langue).
5. p = 1.