Questions marquées «nfa»

Une langue régulière donnée contient-elle un sous-ensemble infini sans préfixe?

Un ensemble de mots sur un alphabet fini est sans préfixe s'il n'y a pas deux mots distincts où l'un est un préfixe de l'autre. La question est: Quelle est la complexité de vérifier si un langage régulier donné en NFA contient un sous-ensemble infini sans préfixe? Réponse (grâce à Mikhail Rudoy,...

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

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