Quelle classe de langues est reconnue par les automates à états finis avec

10

Un DFA ou un NFA lit une chaîne d'entrée avec une seule tête, se déplaçant de gauche à droite. Il semble naturel de s'interroger sur les machines à états finis qui ont plusieurs têtes , chacune se déplaçant à travers l'entrée de gauche à droite, mais pas nécessairement au même endroit dans l'entrée que les autres.

Définissons une machine à états finis avec k têtes comme suit:

Un NFA à tête k est un tuple (Q,Σ,Δ,q0,F) , où:

  • Comme d'habitude, Q est un ensemble fini d'états, Σ est un alphabet fini, q0 est un état initial et F est un ensemble d'états accepteurs. Soit Σε:=Σ∪{ε} le jeu de caractères incluant la chaîne vide.

  • Δ⊆Q×(Σε)k×Q est la relation de transition: une transition(p,(σ1,σ2,…,σk),q) signifie que, si la machine est dans l'étatp , elle peut lire dans(σ1,σ2,…,σk) telle sorte queσi est le caractère suivant pour la têtei (ouε si cette tête ne bouge pas), puis passez à l'étatq .

Une exécution de ce type de machine (tout chemin partant de l'état de départ et se terminant dans un état acceptant) entraîne non pas une chaîne, mais k chaînes différentes (formées en concaténant les caractères le long de l'exécution). Ensuite, nous disons que l'exécution est valide si les k chaînes sont identiques.

Le langage de la machine est l'ensemble des chaînes w tel qu'il existe une série valide de la machine où les k chaînes produites le long de cette série sont toutes égales à w .

Question: Quelle est la classe de langues reconnues par de telles machines? At-il été étudié?

{anbn∣n∈N}
23Exemple NFA à 2 têtes

σ1/σ2(p,(σ1,σ2),q)

k

fl.formal-languages automata-theory regular-language nfa 6005
la source
2
En regardant un peu autour, je vois des automates multi-têtes mentionnés dans arxiv.org/abs/0906.3051 : leur définition concerne les automates bidirectionnels, mais ils définissent également la variante unidirectionnelle. N'y a-t-il pas quelque chose d'utile dans ce document? ou dans ses références, par exemple, sciencedirect.com/science/article/pii/S0304397509006288
a3nm
2
anbncn#
2
Merci pour les références papier - c'était juste une curiosité oiseuse et je n'avais pas vérifié la littérature. Si personne d'autre ne le fait, je vais lire de la littérature et répondre avec une réponse qui résume les résultats connus.
6005

Réponses:

5

Ce modèle est l'un des modèles standard de la théorie des automates et il a été examiné par certains chercheurs.

Les références données dans le premier commentaire sont de très bons points de départ.

Lorsque la tête est bidirectionnelle, les classes de langages reconnues par de tels modèles sont identiques aux classes d'espace logarithmique. Cependant, lorsque la tête est à sens unique, alors, à ma connaissance, nous n'avons pas une caractérisation exacte similaire, mais, nous avons certains résultats incomparables et certaines hiérarchies basées sur le nombre de têtes.

Si vous êtes intéressé, je vous recommande de vérifier également les versions alternées, probabilistes et quantiques des automates à têtes multiples. De tels modèles peuvent être très intéressants même en utilisant une seule tête, car le calcul est divisé en différents chemins, puis, dans chaque chemin, la tête peut accéder à différentes parties des entrées.

Quelques références génériques:

Alternance

Calcul probabiliste

Calcul probabiliste et quantique

Modèles associés: automates multi-compteurs et automates utilisant des galets.

Abuzer Yakaryilmaz
la source