Cours 1 : Introduction

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

  digraph {
    rankdir=LR;
    q_0 -> q_F[label="a"];
    q_F -> q_F[label="b"];
    q_F -> q_0[label="a"];
  }
Automate fini (NFA) :

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

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

  • $𝛿 ⊆ Q \times (𝛴 ∪ \lbrace 𝜀 \rbrace) \times Q$

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

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

Sémantique

Exécution de $𝒜$ :

Une séquence $q_0 ⟶^{a_1} ⋯ ⟶^{a_n} q_n$ où :

  • $∀i, (q_i, a_{i+1}, q_{i+1})∈𝛿$
Exécution initiale :

$q_0∈I$

Exécution finale :

$q_n∈F$

Exécution acceptante :

initiale et finale

Notations :

  • $q_0 ⟶^{a_1 ⋯ a_n} q_n$
  • On étend $𝛿$ aux mots : $q_n ∈ 𝛿(q_0, a_1 ⋯ a_n)$
Langage de $𝒜$ :
\[\lbrace w∈𝛴^\ast \mid ∃q_0∈I, q_f∈F; q_0 ⟶^{w} q_f \rbrace\]
Un automate est sans $𝜀$-transitions :

si $𝛿 ⊆ Q \times 𝛴 \times Q$

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

\[\vert 𝒜 \vert ≝ \max(\vert Q \vert, \vert 𝛿 \vert)\]

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 $𝒜’ = ⟨Q’, 𝛴, 𝛿’, I’, F’⟩$

où :

  • $Q’=Q$
  • $I’=I$
  • $F’= \lbrace q \mid 𝛿(q, 𝜀) ∩ F ≠ ∅ \rbrace$
  • $𝛿’ ≝ \lbrace (q, a, q’) \mid ∃q’‘∈ 𝛿(q,𝜀); (q’’, a, q’)∈𝛿 \rbrace$
  1. $L(𝒜’) = L(𝒜)$

Soit $w=a_1 ⋯ a_n∈L(𝒜)$, $a_i∈𝛴∪ \lbrace 𝜀 \rbrace$ accepté par

\[q_0 ⟶^{a_1} ⟶ ⋯ ⟶^{a_n} q_n\]

En identifiant les $a_i=𝜀$, et notant par une notation primée les $a_i=a’_i≠𝜀$, et les états correspondants.

On trouve dans $𝒜’$ l’exécution :

\[q_0 ⟶^{a'_1} ⟶ ⋯ ⟶^{a'_r} q'_r\]

et $w$ est accepté.

  1. $\vert 𝒜’ \vert ∈ O(\vert 𝒜 \vert^2)$ et peut être construit en $O(\vert 𝒜 \vert^2)$

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

Exemples :

$𝛴 = \lbrace 1, ⋯, n \rbrace$

Automate $𝒜_n$ qui reconnaît l’ensemble des sous-mots de $1 ⋯ n$ :

digraph {
        rankdir=LR;
        kplus[label="k+1"];
        ⋯2[label="⋯"];
		0 -> 1[label="1"];
        1 -> 2[label="𝜀"];
        1 -> 2[label="2"];
        1 -> 3[label="𝜀"];
        1 -> k[label="𝜀"];
        2 -> 3[label="3"];
        2 -> 3[label="𝜀"];
        2 -> k[label="𝜀"];
        3 -> ⋯;
        3 -> k[label="𝜀"];
        ⋯ -> k;
        k -> kplus[label="𝜀"];
        k -> kplus[label="k+1"];
        kplus -> ⋯2;
        ⋯2 -> N[label="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 :

$∀q, a, 𝛿(q, a) ≤ 1$

Complet :

$∀q, a, 𝛿(q, a) ≥ 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$ :

$\vert q \cdot w \vert ≝ \vert 𝛿(q, w) \vert= 1$

Si $𝒜$ est un $DFA$ complet :

\[w∈L(𝒜) ⟺ q_0 \cdot w ∈ F\]

DONC

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

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$

\[𝛿≝ \lbrace (q_1, q_2), a, (q'_1, q'_2) \mid (q_1, a, q'_1)∈𝛿_1 \text{ et } (q_2, a, q'_2)∈𝛿_2 \rbrace \\ ∪ \lbrace (q_1, q_2), 𝜀, (q_1, q'_2) \mid (q_2, 𝜀, q'_2)∈𝛿_2 \rbrace \\ ∪ \lbrace (q_1, q_2), 𝜀, (q'_1, q'_2) \mid (q_1, 𝜀, q'_1)∈𝛿_1 \rbrace\]
  • 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 :

      digraph {
    rankdir=LR;
    q_0 -> q_1[label="a"];

  }

    devient

      digraph {
    rankdir=LR;
    q_0 -> ⋯[label="𝜇(a)"];
    ⋯ -> q_1
  }

  • Fermeture par morphisme inverses : $L⊆𝛥^\ast$

    \[𝜇^{-1}(L) ≝ \lbrace u∈𝛴^\ast \mid 𝜇(u)∈L \rbrace\] 
      digraph {
    rankdir=LR;
    q_0 -> ⋯[label="𝜇(a)"];
    ⋯ -> q_1
  }

    devient

      digraph {
    rankdir=LR;
    q_0 -> q_1[label="a"];
  }
    \[𝛿' ≝ \lbrace (q,a,q') \mid q'∈𝛿(q,𝜇(a)) \rbrace\]

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

  • Shuffle (mélange) :

    \[u \bot v ≝ \lbrace u_1 v_1 ⋯ v_k u_2 ⋯ u_n v_n \mid u_i ∈𝛴^\ast, v_i∈𝛴^\ast, u = u_1 ⋯ u_n, v = v_1 ⋯ v_n \rbrace\] \[L \bot M = \bigcup_{u∈L, v∈M} u \bot v\]

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

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

    $𝒜 ≝ ⟨Q_1 \times Q_2, 𝛴, 𝛿, I_1 \times I_2, F_1 \times F_2⟩$

    \[𝛿 ≝ \lbrace ((q_1, q_2), a, (q'_1, q_2)) \mid a∈𝛴 ∪ \lbrace 𝜀 \rbrace , (q_1, a, q'_1) ∈ 𝛿_1, q_2 ∈Q\rbrace \\ ∪ \lbrace ((q_1, q_2), a, (q_1, q'_2)) \mid a∈𝛴 ∪ \lbrace 𝜀 \rbrace , (q_2, a, q'_2) ∈ 𝛿_2, q_1 ∈Q\rbrace\]

Expressions rationnelles

Syntaxe :

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

\[E := ∅ \vert 𝜀 \vert a∈𝛴 \vert E\cdot E \vert E+E \vert E^\ast\]

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) ⊆ 𝛴^\ast$ est défini inductivement
  • $L(∅) ≝ ∅$
  • $L(𝜀) ≝ \lbrace 𝜀 \rbrace$
  • $L(a) ≝ \lbrace a \rbrace$
  • $L(E_1 \cdot E_2) ≝ L(E_1) \cdot L(E_1)$
  • $L(E_1 + E_2) ≝ L(E_1) ∪ L(E_1)$
  • $L(E_1^\ast) ≝ L(E_1)^\ast$

NB :

  • $L(𝜀) = L(∅^\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

    \[𝜇:𝛴⟶Rat(𝛴^\ast) \\ 𝜇(𝜀)=\lbrace 𝜀 \rbrace \\ 𝜇(uv) = 𝜇(u) \cdot 𝜇(v)\]

Théorème de Kleene

Th de Kleene :

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

$Rat(𝛴^\ast) ⊆ Rec(𝛴^\ast)$ :

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

automate standard $𝒜_E$ :

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

$𝒜_∅$ :

  digraph {
    rankdir=LR;
    q_0; q_f;
  }

$𝒜_𝜀$ :

  digraph {
    rankdir=LR;
    q_0 -> q_f[label="𝜀"];
  }

$𝒜_a$ :

  digraph {
    rankdir=LR;
    q_0 -> q_f[label="a"];
  }

$𝒜_{E_1 \cdot E_2}$ :

  digraph {
    rankdir=LR;
    q_0 -> 𝒜_1;
    𝒜_1 -> 𝜀;
    𝜀 -> 𝒜_2;
  }

$𝒜_{E_1 + E_2}$ :

  digraph {
    rankdir=LR;
    q_0 -> 𝒜_1;
    𝒜_1 -> q_f;
    q_00 -> 𝒜_2;
    𝒜_2 -> q_ff;
    q_0 -> q_00[label="𝜀"];
    q_ff -> q_f[label="𝜀"];
  }

$𝒜_{E^\ast}$ :

  digraph {
    rankdir=LR;
    q_0 -> 𝒜_1;
    𝒜_1 -> q_f;
    q_00 -> q_0[label="𝜀"];
    q_f -> q_ff[label="𝜀"];
    q_f -> q_0[label="𝜀"];
    q_0 -> q_ff[label="𝜀"];
  }

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$ : \(\vert Q \vert ∈ O(\vert E \vert)\)
  • Construction de Glushkov : \(\vert Q \vert= \Vert E \Vert + 1\)
  • Construction d’Antimirov : \(\vert Q \vert ≤ \Vert E \Vert + 1\)
  • Construction d’Hromovic : \(O(\vert E \vert \log \log \vert E \vert)\)

$Rec(𝛴^\ast) ⊆ Rat(𝛴^\ast)$ :

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

\[𝒜 = (Q, 𝛴, 𝛿, I, F)\]

La matrice d’adjacence donne une table des

$L_{q,q’} ≝$

  • $\lbrace a \rbrace$ si $(q, a, q’)∈𝛿$
  • $∅$ sinon
  • $\lbrace 𝜀 \rbrace$ si $q=q’$

On ordonne les états de $1$ à $\vert Q \vert$

\[L_{q,q'}^{(k)} ≝ \lbrace a_1 ⋯ a_n ∈ 𝛴^\ast \mid q ⟶^{a_1} q_1 ⟶ ⋯ ⟶^{a_n} q'; ∀i, q_i ≤ k \rbrace\] \[L(𝒜) = \bigcup_{q∈I, q'∈F} L_{q,q'}^{\vert Q \vert}\]

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

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

\[L_{q,q'}^{(k+1)}= L_{q,q'}^{(k)} ∪ L_{q,k+1}^{(k)}(L_{k+1,k+1}^{(k)})^\ast L_{k+1,q'}^{(k)}\]

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

\[S_k = \max_{q,q'} \vert L_{q,q'}^{(k)} \vert \\ S_0 ≤ 3 \\ S_{k+1} ≤ 4S_k + 4\]

Exemple :

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

Automate $𝒜_n$ avec :

\[𝛴_n ≝ \lbrace a_{i,j} \mid 1≤i,j≤n \rbrace \\ Q_n = ⟦1,n⟧ \\ I_n = F_n = \lbrace 1 \rbrace \\ 𝛿_n = \lbrace (i, a_{i,j}) \mid 1 ≤ i,j ≤n \rbrace\]

Relations rationnelles

Transducteur fini :

un tuple $𝜏 ≝ ⟨Q, 𝛴, 𝛥, 𝛿, I, F⟩$, où :

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

Sémantique :

Une exécution sur $(w,w’)∈𝛴^\ast \times 𝛥^\ast$

$∃n;$

  • $w = u_1 u_2 ⋯ u_n ∈ 𝛴^\ast$

  • $w’ = v_1 v_2 ⋯ v_n ∈ 𝛥^\ast$

Exécution acceptante :

si $q_0∈I$, $q_n∈F$

La relation définie par $𝜏$ est

\[R(𝜏) = \lbrace (w, w') \mid 𝛿(q_0, w, w')∩F≠∅ ⊆ 𝛴^\ast \times 𝛥^\ast \rbrace\]

Exs :

Relation identité :

  digraph {
    rankdir=LR;
    q_0 -> q_0[label="a,a"];
  }

Relation $L\times \lbrace 𝜀 \rbrace$ :

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

Relation $R_𝜇 ≝ \lbrace (u, 𝜇(u)) \mid u∈𝛴^\ast \rbrace$ :

  digraph {
    rankdir=LR;
    q_0 -> q_0[label="a,𝜇(a)"];
  }

Relation $R^{-1} ≝ \lbrace (w’, w) \mid (w,w’)∈R \rbrace$ :

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

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

Preuve :

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

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

on construit $𝒜’$ tq

\[L(𝒜') = R(L) \\ = \lbrace w' \mid ∃ w∈L; (w, w') ∈ R \rbrace\]

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

\[𝛿 ⊆ Q \times 𝛴 \times \lbrace 𝜀 \rbrace \times Q ∪ Q \times \lbrace 𝜀 \rbrace \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$

\[𝛿 = \lbrace (q_1, q_2), 𝜀, (q'_1, q_2) \mid ∃a∈𝛴; (q_1, a, q'_1) ∈ 𝛿_1, (q_2, a, 𝜀, q_2) ∈ 𝛿_2 \rbrace \\ ∪ \lbrace (q_1, q_2), b, (q_1, q'_2) \mid (q_2, 𝜀, b, q'_2) ∈ 𝛿_2 \rbrace\]

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

Leave a comment