Questions marquées «automata-theory»

Depuis un certain temps, je suis curieux de voir les machines de Turing avec exactement une bande et exactement 3 états (à savoir l'état de démarrage , l'état d'acceptation et l'état de rejetq0q0q_0qacceptqacceptq_{accept}qrejectqrejectq_{reject} ). Notez que j'autorise les alphabets de bande...

Soit un alphabet fini. Pour un langage donné le monoïde syntaxique est une notion bien connue en théorie formelle du langage. De plus, un monoïde reconnaît un langage ssi il existe un morphisme tel que .L ⊆ A ∗ M ( L ) M L φ : A ∗ → M L = φ - 1 ( φ ( L ) ) )UNEAAL ⊆ A∗L⊆UNE∗L \subseteq A^{\ast} M(...

S'il y a des résultats sur la résolution des problèmes de langage formel en utilisant l'analyse mathématique, les mathématiques continues. Par exemple, résoudre le problème de non-vacuité d'intersection pour une langue sans contexte et une langue