Comment mesurer la complexité d'un langage rationnel ?
La complexité d’un langage rationnel L peut se mesurer de diverses façons ; dans le cadre des automates finis déterministes, il est nature de la définir comme le nombre d’états de l’automate déterministe complet minimal reconnaissant ce langage. Par le théorème de Myhill-Nerode, c'est aussi le nombre de résiduels ou quotients gauches du langage.
Qu'est-ce que le théorème de l'automate fini déterministe minimal ?
Ce théorème a un intérêt théorique puisqu'il donne une caractérisation intrinsèque de l'automate minimal reconnaissant un langage donné. En effet, les états de l'automate fini déterministe minimal reconnaissant un langage rationnel sont en bijection avec les classes d'équivalence de la relation 2.
Comment reconnaître un langage rationnel ?
Cette définition est bien équivalente à la première pour l'ensemble des mots. Si est un langage rationnel, alors est reconnu par son monoïde syntaxique (il suffit de prendre pour la projection canonique et pour l'ensemble des classes d'équivalence incluses dans ). Réciproquement, si est un langage reconnu par un monoïde fini , alors l'automate où:
Pourquoi deux automates finis déterministes sont-ils équivalents ?
Deux automates finis déterministes sont équivalents s'ils reconnaissent le même langage. C'est un résultat remarquable de la théorie qu'il existe, pour tout automate fini, un seul automate fini déterministe minimal (c'est-à-dire ayant un nombre minimal d'état) qui est équivalent à l'automate donné.
Cours Capteurs et Satellites
LP_Final draft _clean_07112021_final
Le programme d’admission international de ParisTech prend de
Parler est un besoin écouter est un art
Chapitre I Généralités sur les communications par satellites
SYSTEMES DE POURSUITE POUR LA TRANSMISSION PAR
Etude et Modélisation de la Transmission dans les Satellites Lasers
Pharmacodépendance
Rapport Soumission chimique
Comprendre la déterminisation dun automate fini (didacticiel)
#18 Théorie des Langages et Compilation
