Quel est le nombre de langues acceptées par un DFA de taille

19

La question est simple et directe: pour un fixe n, combien de langues (différentes) sont acceptées par un DFA de taille n (c'est-à-dire n états)? Je vais déclarer officiellement ceci:

Définissez un DFA comme (Q,Σ,δ,q0,F) , où tout est comme d'habitude et est une fonction (éventuellement partielle). Nous devons établir cela, car parfois seules les fonctions totales sont considérées comme valides.δ:Q×ΣQ

Pour chaque , définissez la relation (d'équivalence) sur l'ensemble de tous les DFA comme: if et .n A n B | A | = | B | = n L ( A ) = L ( B )n1nUNEnB|UNE|=|B|=nL(UNE)=L(B)

La question est alors: pour un donné , quel est l'indice de ? Autrement dit, quelle est la taille de l'ensemble ?n { L ( A ) A  est un DFA de taille  n }nn{L(UNE)UNE est un DFA de taille n}

Même lorsque δ est une fonction totale, cela ne semble pas être un compte facile (pour moi, au moins). Le graphique peut ne pas être connecté, et les états du composant connecté contenant l'état initial peuvent tous être acceptables, donc, par exemple, il existe de nombreux graphiques de taille n acceptant Σ . Idem avec d'autres combinaisons triviales pour la langue vide et d'autres langues dont le DFA minimal a moins de n états.

Une récursion (naïve) ne semble pas fonctionner non plus. Si nous prenons un DFA de taille et ajoutons un nouvel état, alors, si nous voulons garder le déterminisme et rendre le nouveau graphe connecté (pour essayer d'éviter les cas triviaux), nous devons supprimer une transition pour connecter le nouvel état, mais dans ce cas, nous risquons de perdre la langue d'origine.k

Des pensées?

Remarque. J'ai mis à jour la question à nouveau, avec une déclaration officielle et sans les éléments distrayants précédents.

Janoma
la source
Juste pour clarifier: voulez-vous dire "combien de langues différentes peut-on définir en utilisant états?", Où une langue est définie en utilisant états s'il existe un DFA avec états qui l'accepte. De plus, pour les expressions régulières, l'expression régulière "a * aaaaaa" a sûrement> 1 concaténations, mais le DFA n'a besoin que d'un seul état (deux si vous avez besoin d'un récepteur séparé), non? nnn
Evgenij Thorstensen
Excuses: pour l'exemple d'expressions régulières, il doit s'agir de "a a a a a *", car cela autorise tout nombre.
Evgenij Thorstensen
La définition de semble très liée à la notion de "profondeur de point", sauf que ce concept est normalement appliqué aux langages sans étoiles (probablement pour les raisons décrites par @Evgenij Thorstensen). c(r)
mhum
1
Observation triviale: états peuvent être utilisés pour définir au moins 2 n langues différentes. n+12n
Evgenij Thorstensen
2
Nous pouvons obtenir un peu plus, donc semble OK. Mais le nombre d'automates à n états est d'environ n c n 2 n = 2 c n log n + n = 2 Θ ( n log n ) (en supposant | Σ | = c ). Pouvons-nous obtenir 2 ω ( n ) ? 2Ω(n)ncn2n=2cnlogn+n=2Θ(nlogn)|Σ|=c2ω(n)
Kaveh

Réponses:

20

Je pense que cette question a été étudiée précédemment. Mike Domaratzki a rédigé une enquête sur la recherche dans ce domaine: "Énumération des langues formelles", Bull. EATCS, vol. 89 (juin 2006), 113-133: http://www.eatcs.org/images/bulletin/beatcs89.pdf

Hermann Gruber
la source
4
Le document répond précisément à la question posée, à partir de la page 120. C'est la fonction , et le papier donne des limites assez serrées (proche de ce que Kaveh mentionne ci-dessus), bien que je n'aie pas inhalé tous les détails. gk(n)
Evgenij Thorstensen
1
En effet. Ce que nous voulons, c'est alors , ou, par la relation donnée, f k ( n ) , qui est le nombre de DFA minimaux non isomorphes par paires avec n états sur un alphabet à k lettres. Je ne l'ai pas non plus examiné en détail, mais il semble que seules les limites soient connues, pas les quantités exactes. gk(n)fk(n)nk
Janoma
6
Et, du même auteur, nous avons l'article On the Number of Distinct Languages ​​Accepted Finite Automata with n States , qui donne même des calculs explicites pour ( 1 n 10 ), g 2 ( n ) ( 1 n 6 ) et g 3 ( n ) ( 1 n 4 ). g1(n)1n10g2(n)1n6g3(n)1n4
Janoma