Catégorie : Automate

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 résiduels. Exercice Soit $\mathcal{L}$ un langage. Soit $(u_i)_{i \in \mathbb{N}}$ une suite infini de […]

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 […]