Existe-t-il des exemples de lemmes de pompage avec des langues «réelles»?

Question

Le pumping lemma est une propriété de regular languages et de context-free languages. Mais tous les exemples que j'ai vu des choses comme:

L = {0 ^{n n n}: n ≥ 0}

(qui, soit dit en passant, est pas une langage sans contexte).

Mais ce qui m'intéresse est la suivante: y a-t-il des exemples de son utilisation avec des langages réels ou utiles? Je n'ai pas réussi à en trouver. Est-ce une de ces choses ou une valeur purement théorique sans aucune application pratique?

Answer 1

L = {0 ^{n n}: n ≥ 0} étant une langue sans contexte.

correspondant parenthesis dans une expression peut être considérée comme une forme similaire à savoir

L = {(ⁿ) ⁿ: n ≥ 0}

Answer 2

Une utilisation pratique est le fait que tout le monde peut cesser d'essayer de construire un automate fini pour reconnaître la syntaxe de C# ou de Fortran.

Une autre utilisation pratique est le fait que tout le monde peut arrêter d'essayer de construire un automate à pile pour reconnaître la sémantique de C# ou de Fortran. (Même si dans Fortran si vous mal orthographiez un nom de variable, vous obtenez une nouvelle variable gratuitement, la nouvelle variable ne fonctionnera probablement pas avec les opérateurs que vous avez codés lorsque vous vouliez nommer l'une de vos variables déclarées.)

Answer 3

ceci de ces choses ou valeur purement théorique avec absolument aucune application pratique? "

Hrm. Qu'est-ce qu'une application pratique? Vous avez judicieusement étiqueté votre question "informatique-science". Donc, je suppose que votre question vise à demander: « est-il pratique la science à l'ordinateur?

Dans ce cas, la réponse est ...

Bien sûr, il est! Il est enseigné comme une des premières façons de classer différentes classes de complexité de langage, au-delà de simplement "big-O (whateverthehell)" Il montre qu'il y a des problèmes concernant le calcul au-delà du runtime, dans ce cas certains modèles ne peuvent simplement pas calculer certaines fonctions. * -ball introduction aux preuves formelles concernant la théorie des automates

Une énorme partie de l'informatique que la plupart des étudiants en informatique (mes pairs) semblent Vouloir éviter est la Théorie du Calcul, une classification que les lemmes de pompage relèvent évidemment.

Le fait, on l'espère, est que la théorie du calcul, qu'elle soit ou non, est fondamentale pour l'informatique. Ne pas comprendre l'idée de classes de complexité différentes (le big-O ne le coupe pas vraiment) ne sera pas la mort de l'informaticien, mais il cachera une partie considérable du champ de sa vue.

* Oui, le problème d'arrêt est généralement affiché en premier, mais il ne l'est jamais la première fois. En ce qui concerne peut-être l'interprétation plus cynique de votre question, dans laquelle vous voulez dire "est-ce que n'importe quel logiciel utilise vraiment ceci?", Ma réponse est bien sûr que non. Cela fait partie du fondement du calcul, pas de ses applications. Cela ne veut pas paraître dédaigneux de ses applications, pas du tout. Les deux sont d'égale valeur noble.

Answer 4

ce programme python est valide:

print ((((((((((((((((((((((((1)))))))))))))))))))))))) 

ainsi que toutes les autres déclarations équivalentes avec une quantité égale de ( à gauche et ) sur le côté droit.

Vous ne pouvez pas générer une expression régulière pour vérifier cela, vous devez donc utiliser un analyseur.

Ce n'est pas du tout théorique. C'est la raison pour laquelle vous ne pouvez pas utiliser regex pour analyser HTML.