Introduction

Automate :

modèle extrêmement réduit de MT : ne peut pas écrire sur le ruban, et va toujours à droite

MAIS : en contrepartie : il y a très peu de propriétés qu’on ne peut pas décider sur les langages rationnels (contrairement aux MT, où Riesz nous condamne)⟶ bonnes propriétés algorithmiques

Langages rationnels = une boîte à outils utilisée en

• Algorithmique
• Logique
• Intelligence artificielle

Différents points de vue équivalents :

1. Reconnaissance par automates :

   ⟶ opérationnel

2. Expressions rationnelles :

   ⟶ dénotationnel

3. Logique :

• Logique du premier ordre : ensemble des modèles considérés = les mots finis

• ordre + prédicat unaire ⟶ logique du premier ordre

• quantification sur les ensembles des propositions ⟶ logique monadique du second ordre : équivalent aux langages rationnels

1. Algèbre :

• Reconnaissance par monoïdes finis : homomorphisme entre le monoïde libre et des quotients de monoïde (en fonction des états de l’automate)

NB : points de vue équivalents, mais passer d’une représentation à l’autre : plus ou moins difficile :

Exs :

• passer d’un automate à une ER : exponentiel
• passer d’une logique MSO à un automate/ER : tour d’exponentielle

PUIS : extension des langages rationnels qui capturent une classe de langages plus large

⟶ Langages Algébriques :

Différents points de vue :

1. Automates à pile
2. Grammaires algébriques

• ex: pour les compilateurs : on écrit une grammaire algébrique, puis traduction en automates à piles

Ex :

Programme en assembleur ⟶ pile d’appels ⟶ se modélise naturellement à l’aide d’automates à pile

Automates finis

Automate fini (NFA) :

Un tuple $𝒜=⟨Q,𝛴,𝛿,I,F⟩$ où :

• $Q$ est un ens. fini d’états
• $𝛴$ un alphabet fini

• $𝛿\subseteq Q\times (𝛴\cup \{𝜀\})\times Q$

  NB : inclure $𝜀$ revient à autoriser la MT à rester sur place

• $I,F\subseteq Q$ ens. d’états intiaux et finals

Sémantique

Exécution de $𝒜$ :

Une séquence $q_0{⟶}^{a_1}\cdots {⟶}^{a_n}{q}_n$ où :

• $\forall i,(q_i,a_{i+1},q_{i+1})\in 𝛿$

Exécution initiale :

$q_0\in I$

Exécution finale :

$q_n\in F$

Exécution acceptante :

initiale et finale

Notations :

• $q_0{⟶}^{a_1\cdots a_n}{q}_n$
• On étend $𝛿$ aux mots : $q_n\in 𝛿(q_0,a_1\cdots a_n)$

Langage de $𝒜$ :

$$\{w\in {𝛴}^{\ast }\mid \exists q_0\in I,q_f\in F;q_0{⟶}^w{q}_f\}$$

Un automate est sans $𝜀$-transitions :

si $𝛿\subseteq Q\times 𝛴\times Q$

Réprésentation : par listes d’adjacences, donc

Lemme : Pour tout NFA, on peut construire un NFA équivalent sans $𝜀$-transitions de taille $O(n^2)$ en temps $O(n^2)$

Preuve :

Soit $𝒜=⟨Q,𝛴,𝛿,I,F⟩$.

On construit ${𝒜}^{\prime }=⟨Q^{\prime },𝛴,{𝛿}^{\prime },I^{\prime },F^{\prime }⟩$

où :

• $Q^{\prime }=Q$
• $I^{\prime }=I$
• $F^{\prime }=\{q\mid 𝛿(q,𝜀)\cap F\ne \varnothing \}$
• ${𝛿}^{\prime }\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{(q,a,q^{\prime })\mid \exists q^{\prime }‘\in 𝛿(q,𝜀);(q^{″},a,q^{\prime })\in 𝛿\}$

1. $L({𝒜}^{\prime })=L(𝒜)$

Soit $w=a_1\cdots a_n\in L(𝒜)$, $a_i\in 𝛴\cup \{𝜀\}$ accepté par

En identifiant les $a_i=𝜀$, et notant par une notation primée les $a_i=a_i^{\prime }\ne 𝜀$, et les états correspondants.

On trouve dans ${𝒜}^{\prime }$ l’exécution :

et $w$ est accepté.

1. $|{𝒜}^{\prime }|\in O(|𝒜{|}^2)$ et peut être construit en $O(|𝒜{|}^2)$

Pour chaque état, on trouve les états accessibles par une séquence d’$𝜀$-transitions ⟹ $O(n^2)$

Exemples :

$𝛴=\{1,\cdots ,n\}$

Automate ${𝒜}_n$ qui reconnaît l’ensemble des sous-mots de $1\cdots n$ :

(avec clôture transitive pour les $𝜀$-transitions)

Complexité : $\frac{n(n-1)}{2}$

Propriétés de clôture

Prop : Les langages reconnaissables par automates sont fermés par :

• union (juxtaposition des automates, avec complexité $O(n_1+n_2)$)
• concaténation (on lie les états finals du premier aux états initiaux du second par des $𝜀$-transitions en passant par un état intermédiaire (complexité $O(n_1+n_2)$)

• l’étoile de Kleene (on lie les états finals aux états initiaux par des $𝜀$-transitions en passant par un état intermédiaire (complexité $O(n)$)

  • NB : on passe par un état intermédiaire pour ne pas rajouter de boucles supplémentaires à l’intérieur de l’automate

NB : pas fermé par complémentation, si l’automate n’est pas déterministe ET complet.

Déterministe :

$\forall q,a,𝛿(q,a)\le 1$

Complet :

$\forall q,a,𝛿(q,a)\ge 1$

Pourquoi ça marche avec les automates déterministes complets ?

⟶ car pour tout état $q$, il existe une unique exécution sur $w$ commençant en $a$ :

$|q\cdot w|\stackrel{\scriptscriptstyle\mathrm{def}}{=}|𝛿(q,w)|=1$

Si $𝒜$ est un $DFA$ complet :

DONC

Prop : Pour un automate $𝒜$, on peut construire un automate reconnaissant $𝛴\mathrm{\setminus }L(𝒜)$ de taille $O(2^{|Q|}|𝛴|)$ en temps $O(2^{|Q|}|𝛴|)$

Déterminiser l’automate prend un temps exponentiel en le nombre d’états, et il n’y a pas moyen de faire mieux.

• Intersection :

On n’est pas fou, on ne va le faire en utilisant l’union et la complémentation (complémentation exponentielle !), il y a bien plus efficace avec l’automate produit (coût quadratique, et on ne peut pas faire mieux) :

$Q=Q_1\times Q_2,I=I_1\times I_2,F=F_1\times F_2$

• Transposition : en $O(n)$, trivialement

Morphisme :

$$𝜇:𝛴⟶{𝛥}^{\ast }$$

défini sur les générateur $𝜇:𝛴⟶{𝛥}^{\ast }$, puis étendu par propriété universelle en $𝜇:{𝛴}^{\ast }⟶{𝛥}^{\ast }$

• Fermeture par morphisme :

  devient

• Fermeture par morphisme inverses : $L\subseteq {𝛥}^{\ast }$

  $${𝜇}^{-1}(L)\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{u\in {𝛴}^{\ast }\mid 𝜇(u)\in L\}$$

  devient

  $${𝛿}^{\prime }\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{(q,a,q^{\prime })\mid q^{\prime }\in 𝛿(q,𝜇(a))\}$$

  On montre que ${𝜇}^{-1}(L(𝒜))\subseteq L({𝒜}^{\prime })$ (l’autre inclusion étant triviale)

• Shuffle (mélange) :

  $$u\mathrm{\perp }v\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{u_1{v}_1\cdots v_k{u}_2\cdots u_n{v}_n\mid u_i\in {𝛴}^{\ast },v_i\in {𝛴}^{\ast },u=u_1\cdots u_n,v=v_1\cdots v_n\}$$ $$L\mathrm{\perp }M=\bigcup _{u\in L,v\in M}u\mathrm{\perp }v$$

  Prop : Les langages reconnaissables sont fermés par mélange

  Pour ${𝒜}_1$ et ${𝒜}_2$, on construit :

  $𝒜\stackrel{\scriptscriptstyle\mathrm{def}}{=}⟨Q_1\times Q_2,𝛴,𝛿,I_1\times I_2,F_1\times F_2⟩$

  $$\begin{array}{c}𝛿\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{((q_1,q_2),a,(q_1^{\prime },q_2))\mid a\in 𝛴\cup \{𝜀\},(q_1,a,q_1^{\prime })\in {𝛿}_1,q_2\in Q\}\\ \cup \{((q_1,q_2),a,(q_1,q_2^{\prime }))\mid a\in 𝛴\cup \{𝜀\},(q_2,a,q_2^{\prime })\in {𝛿}_2,q_1\in Q\}\end{array}$$

Expressions rationnelles

Syntaxe :

L’ensemble des expressions rationnelles sur $𝛴$ est l’ensemble des termes pour la syntaxe

NB : les opération d’union, de concaténation et l’étoile de Kleene sont aussi appelées “opérations rationnelles”.

Sémantique :

• $L(E)\subseteq {𝛴}^{\ast }$ est défini inductivement
• $L(\varnothing )\stackrel{\scriptscriptstyle\mathrm{def}}{=}\varnothing$
• $L(𝜀)\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{𝜀\}$
• $L(a)\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{a\}$
• $L(E_1\cdot E_2)\stackrel{\scriptscriptstyle\mathrm{def}}{=}L(E_1)\cdot L(E_1)$
• $L(E_1+E_2)\stackrel{\scriptscriptstyle\mathrm{def}}{=}L(E_1)\cup L(E_1)$
• $L(E_1^{\ast })\stackrel{\scriptscriptstyle\mathrm{def}}{=}L(E_1{)}^{\ast }$

NB :

• $L(𝜀)=L({\varnothing }^{\ast })$

• l’ensemble des langages rationnels est le plus petit ensemble contenant les langages finis sur $𝛴$ et fermé par union, concaténation, et étoile de Kleene.

• Clôture par substitution rationnelle : à chaque lettre on associe une expression rationnelle

  $$\begin{array}{c}𝜇:𝛴⟶Rat({𝛴}^{\ast })\\ 𝜇(𝜀)=\{𝜀\}\\ 𝜇(uv)=𝜇(u)\cdot 𝜇(v)\end{array}$$

Théorème de Kleene

Th de Kleene :

$$\underset{\text{ lang. déf. par expr. rat}}{\underbrace{Rat({𝛴}^{\ast })}}=\underset{\text{ lang. rec. par automates}}{\underbrace{Rec({𝛴}^{\ast })}}$$

$Rat({𝛴}^{\ast })\subseteq Rec({𝛴}^{\ast })$ :

Construction de THOMSON par induction sur $E$ : on obtient un automate standard ${𝒜}_E$ de taille $O(|E|)$

automate standard ${𝒜}_E$ :

$|I|=|F|=1$, et pas de transition entrantes dans $I$ ni de transition sortante de $F$

${𝒜}_{\varnothing }$ :

${𝒜}_{𝜀}$ :

${𝒜}_a$ :

${𝒜}_{E_1\cdot E_2}$ :

${𝒜}_{E_1+E_2}$ :

${𝒜}_{E^{\ast }}$ :

On définit la taille alphabétique $\Vert E\Vert$ d’une ER $E$ par récurrence, de manière naturelle.

• Construction de Thomson par induction sur $E$ : $|Q|\in O(|E|)$
• Construction de Glushkov : $|Q|=\Vert E\Vert +1$
• Construction d’Antimirov : $|Q|\le \Vert E\Vert +1$
• Construction d’Hromovic : $O(|E|\log \log |E|)$

$Rec({𝛴}^{\ast })\subseteq Rat({𝛴}^{\ast })$ :

Construction par élimination d’états : Mc Naughton Yamada :

La matrice d’adjacence donne une table des

$L_{q,q^{\prime }}\stackrel{\scriptscriptstyle\mathrm{def}}{=}$

• $\{a\}$ si $(q,a,q^{\prime })\in 𝛿$
• $\varnothing$ sinon
• $\{𝜀\}$ si $q=q^{\prime }$

On ordonne les états de $1$ à $|Q|$

Montrons que les langages $L_{q,q^{\prime }}^{(k)}$ sont rationnels.

Par réc sur $k$, le cas de base étant trivial.

Cette construction se fait en $2^{O(|Q|)}$

Exemple :

On va construire un automate tel qu’il n’y a pas d’ER de taille inférieure à $2^{𝛺(|Q|)}$

Automate ${𝒜}_n$ avec :

Relations rationnelles

Transducteur fini :

un tuple $𝜏\stackrel{\scriptscriptstyle\mathrm{def}}{=}⟨Q,𝛴,𝛥,𝛿,I,F⟩$, où :

• $Q$ ens. fini d’états
• $𝛴,𝛥$ alphabets finis
• $𝛿\subseteq Q\times {𝛴}^{\ast }\times {𝛥}^{\ast }\times Q$ fini
• $I,F\subseteq Q$ ens. intiaux et finals

Sémantique :

Une exécution sur $(w,w^{\prime })\in {𝛴}^{\ast }\times {𝛥}^{\ast }$

$\exists n;$

• $w=u_1{u}_2\cdots u_n\in {𝛴}^{\ast }$

• $w^{\prime }=v_1{v}_2\cdots v_n\in {𝛥}^{\ast }$

Exécution acceptante :

si $q_0\in I$, $q_n\in F$

La relation définie par $𝜏$ est

Exs :

Relation identité :

Relation $L\times \{𝜀\}$ :

On remplace les transitions étiquetées par $a$ dans l’automate d’origine et on les étiquette par $(a,𝜀)$

Relation $R_{𝜇}\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{(u,𝜇(u))\mid u\in {𝛴}^{\ast }\}$ :

Relation $R^{-1}\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{(w^{\prime },w)\mid (w,w^{\prime })\in R\}$ :

On remplace les transitions étiquetées par $(w,w^{\prime })$ dans le transducteur d’origine et on les étiquette par $(w^{\prime },w)$

Th : Les langages rationnels sont fermés par relations rationnelles.

Preuve :

Soit $𝒜$ tq $L(𝒜)=L$

et $𝜏$ tq $R(𝜏)=R$

on construit ${𝒜}^{\prime }$ tq

Lemme : $R=R(𝜏)$, où

$$𝛿\subseteq Q\times 𝛴\times \{𝜀\}\times Q\cup Q\times \{𝜀\}\times 𝛥\times Q$$

Dém : trivial

NB : Pour $R({𝛴}^{\ast })$, il suffit d’oublier la première composante dans le transducteur d’origine.

$Q=Q_1\times Q_2,I=I_1\times I_2,F=F_1\times F_2$

ça généralise ce qu’on a fait précédemment.