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

É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.

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 $0$$k$$i$$A^k[0,i]$$A$$i$$j$$i$$j$$k$$k$

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.

Soit soit un (non déterministe) Automation fini à partir état q 1 , Q F ⊆ Q et δ ⊆ Q × Σ × Q .$A = (Q = \{q_1, \dots, q_n\}, \Sigma, \delta, Q_F)$$q_1$$Q_F \subseteq Q$$\delta \subseteq Q\times\Sigma\times 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 } | .$Q_i(z)$$q_i$$n$$[z^n]Q_i = |\{w \mid |w| = n \wedge w \text{ accepted from } q_i\}|$

Clairement:

$Q_i(z) = \left[ q_i \in Q_F \right] + \sum\limits_{(q_i, a, q_j) \in \delta} x \cdot Q_j(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.$Q_1$$[z^n]Q_1$

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 .$\varepsilon$$x$$a \in \Sigma$$w \in \Sigma^k$$x$$x^k$

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.

$\#\mathsf{NC}^1$