Compter les mots acceptés par une grammaire régulière

26

Étant donné une langue régulière (NFA, DFA, grammaire ou expression régulière), comment peut-on compter le nombre de mots acceptés dans une langue donnée? "Avec exactement n lettres" et "avec au plus n lettres" présentent un intérêt.

Margareta Ackerman a deux articles sur le sujet connexe de l'énumération des mots acceptés par un NFA, mais je n'ai pas pu les modifier pour compter efficacement.

Il semble que la nature restreinte des langues normales devrait rendre leur comptage relativement facile - je m'attends presque à une formule plus qu'à un algorithme Malheureusement, mes recherches n'ont jusqu'à présent rien révélé, donc je dois utiliser les mauvais termes.

Charles
la source
Je suppose que vous voulez dire "nombre de mots acceptant de taille ", ou quelque chose comme ça? sinon, quel est le nombre de mots acceptables pourΣ nΣ
Suresh Venkat

Réponses:

38

Pour un DFA, dans lequel l'état initial est l'état , le nombre de mots de longueur qui se retrouvent dans l'état est , où est la matrice de transfert du DFA (une matrice dans laquelle le nombre dans la ligne et la colonne est le nombre de symboles d'entrée différents qui provoquent une transition de l'état à l'état ). Ainsi, vous pouvez compter les mots acceptant de longueur exactement facilement, même lorsque est modérément grand, simplement en calculant une puissance matricielle et en ajoutant les entrées correspondant aux états accepteurs.k i A k [ 0 , i ] A i j i j k k0kiAk[0,i]Aijijkk

La même chose fonctionne pour accepter des mots de longueur au plus , avec une matrice légèrement différente. Ajoutez une ligne et une colonne supplémentaires de la matrice, avec une dans la cellule qui est à la fois dans la ligne et la colonne, une dans la nouvelle ligne et la colonne de l'état initial, et un zéro dans toutes les autres cellules. L'effet de cette modification de la matrice est d'ajouter un chemin supplémentaire à l'état initial à chaque puissance.k

Cela ne fonctionne pas pour les NFA. Je soupçonne que la meilleure chose à faire est de simplement convertir en DFA, puis d'appliquer l'algorithme d'alimentation de la matrice.

David Eppstein
la source
2
La réponse parfaite: évidente seulement après l'avoir lue.
Charles
1
Cette approche a un temps d'exécution exponentiel dans le pire des cas si vous avez une entrée autre qu'un DFA. N'est-ce pas un problème pour vous, @Charles? Vous semblez inclure des expressions régulières, NFA et grammaires dans vos questions, et demandez également un moyen efficace.
Raphael
17

Soit soit un (non déterministe) Automation fini à partir état q 1 , Q FQ et δ Q × Σ × Q .A=(Q={q1,,qn},Σ,δ,QF)q1QFQδQ×Σ×Q

Soit la fonction génératrice de tous les mots qui peuvent être acceptés à partir de q i , soit le n ième coefficient de son expansion en série [ z n ] Q i = | { w | w | = n w  accepté de  q i } | .Qi(z)qin[zn]Qi=|{w|w|=nw accepted from qi}|

Clairement:

Qi(z)=[qiQF]+(qi,a,qj)δxQj(z)

Résoudre le système d'équation (linéaire) résultant pour (en utilisant Mathematica ou un outil similaire). Alors, [ z n ] Q 1 est la quantité souhaitée.Q1[zn]Q1

Cela remonte à une technique introduite pour les grammaires par Chomsky et Schützenberger (1963); il se transfère facilement vers des automates finis.

Edit: Si vous voulez tenir compte des transitions , laissez simplement le facteur x dans la somme pour la transition correspondante. De même, si vous avez des bords "compressés", c'est-à-dire au lieu du symbole a Σ un mot w Σ k sur une transition, remplacez x par x k .εxaΣwΣkxxk

Raphael
la source
J'apprécie la note historique!
Charles
1
Euh, c'est en fait une méthode qui fonctionne très bien (et est simple, une fois que vous l'avez) dans de nombreuses circonstances. Par exemple, vous pouvez effectuer des CFG exactement de la même manière.
Raphael
1
Je vois, j'ai mal compris. Dans ce cas, si vous voulez lire ceci, je recommande Kuich (1970) que j'ai trouvé plus accessible que le travail de C&S. Il en parle également dans un livre dont je ne me souviens pas.
Raphael
1
Voulez-vous dire que vous pouvez compter des mots de longueur dans une langue régulière en temps polynomial et sans construire DFA? Interrogé sur la complexité de cela sur MO: mathoverflow.net/questions/162186/…n
joro
1
@joro En cas de grammaires non ambiguës, je pense que c'est vrai, oui.
Raphael
7

Je pense que c'est un problème de comptage difficile, voir cet article: Le comptage de la taille des séquences régulières de longueur donnée est # P-complet: S. Kannan, Z. Sweedyk et SR Mahaney. Comptage et génération aléatoire de chaînes dans les langues régulières. Dans ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 551–557, 1995.

Miklós István
la source
1
Le post ci-dessus suppose que la longueur donnée est en unaire. Si à la place la longueur est en binaire, le problème est difficile pour PSPACE. Je dis cela sur la base de la preuve que la décision d'équivalence de deux expressions régulières est difficile pour PSPACE. Dans cette réduction, un reg-ex a été construit pour accepter toutes les chaînes, et l'autre pour accepter toutes les chaînes qui ne sont pas valides en rejetant les historiques de calcul de la machine PSPACE M sur l'entrée w. L'utilisation de cette deuxième expression régulière et de la longueur d'un historique de calcul de M sur w comme entrées pour le problème en question rend cet autre problème PSPACE difficile aussi.
Mikhail Rudoy
3

#NC1

SamiD
la source