Catégorie : Théorie des langages

Critère de non régularité

Auteur de la publication Par Xavier BADIN de MONTJOYE
Date de publication 17 octobre 2021
Catégories Dans Automate, Exercices, Théorie des langages
Aucun commentaire sur Critère de non régularité

On présente ici un critère de non régularité sur les langages. Autrement dit, on s’intéresse à une propriété sur les langages impliquant que ces derniers ne peuvent être reconnus par un automate fini. Cet exercice permet d’avoir une bonne introduction aux

Stabilité des langages rationnels

Auteur de la publication Par Xavier BADIN de MONTJOYE
Date de publication 19 septembre 2021
Catégories Dans Automate, Exercices, Théorie des langages
Aucun commentaire sur Stabilité des langages rationnels

Le but de cet exercice est de présenter plusieurs opérations stables sur les langages rationnels. On suppose connu l’équivalence entre les langages rationnels et les langages reconnaissables par automate fini. Exercice Soit $\mathcal{L}_1$ et $\mathcal{L}_2$ deux langages rationnels sur l’alphabet $\Sigma$. Montrer que les langages suivants sont rationnels. $1)$ $\overline{\mathcal{L}_1} = {\;w \in \Sigma^{*}\;|\;w \notin […]