Cours 3 : Langages algébriques

Langages algébriques

  graph {
    A[label="Système d'équations (algébrique)"];
    B[label="Grammaires algébriques (dénotationnel)"];
    C[label="Automates à piles (opérationnel)"];
    A -- B;
    B -- C;
    C -- A;
  }

Chomsky (1959) : “qu’est-ce qu’une langue (telle que l’anglais) ?”

  • Un langage $L⊆𝛴^\ast$
  • MAIS : ne suffit pas, phrases arbitrairement complexes :

    ex : Si Harry rencontre Sally alors si ⋯ alors, si ⋯ alors

    ⟶ si on remplace les “si” (resp. les “alors”) par des parenthèses ouvrantes (resp. fermantes), on veut une expression bien parenthésée ⟶ pas un langage rationnel

Backus, Naur (1959)

⟶ naissance du langage Algol : premier langage qui peut tourner sur différentes architectures ⟶ première standardisation de la syntaxe d’un langage, pour qu’elle ne dépende plus de l’architecture de l’ordi sur lequel on fait tourner les programmes.

Ex :

if statement then statement else statement

⟶ on se rend compte qu’on parle de la même problématique que Chomsky !


Grammaire :

$G ≝ ⟨N, 𝛴, P, S⟩$ où :

  • $N$ : alphabet fini de non-terminaux (variables)
  • $𝛴$ : alphabet fini de terminaux
  • $N∩𝛴 = ∅$
  • $P⊆ N × (N∪𝛴)^\ast$ : ens. fini de productions (règles)
  • $S∈N$ : axiome (symbole de départ)
A⟶ 𝛼
Relation de dérivation :
⟹ ≝ \lbrace (𝛽A𝛾, 𝛽𝛼𝛾) \mid A ⟶ 𝛼∈ P \text{ et } 𝛾,𝛽∈ (N∪𝛴)^\ast\rbrace
Langage :
  • forme sententielle :

    $\widehat{L}_G(A)≝ \lbrace 𝛽∈(N∪𝛴)^\ast \mid A ⟹^\ast 𝛽 \rbrace$

  • langage :

    $L_G(A) ≝ \lbrace w∈𝛴^\ast \mid A ⟹^\ast w \rbrace = \widehat{L}_G(A) ∩ 𝛴^\ast$

    $L(G) ≝ L_G(S)$

Ex :

$S⟶ aSb \mid 𝜀$

N = \lbrace S \rbrace \\ 𝛴 = \lbrace a, b \rbrace \\ P = \lbrace (S, aSb), (S, 𝜀) \rbrace
S ⟹ aSb \\ ⟹ aaSbb \\ ⟹ ⋯ \\ ⟹ a⋯ab⋯b
L(G) = \lbrace a^n b^n \mid n≥0 \rbrace

NB : Sans perte de généralité, on suppose qu’il y a un seul axiome car on peut toujours s’y ramener : s’il y en a d’autres, on les ajoute à $N$ et on ajoute des règles de transformation de notre axiome de départ en ces autres axiomes.

Ex : Langue naturelle

$N = \lbrace P, SN, SV, N, Pr, Det, SP, PP \rbrace$

$𝛴 = \lbrace elle, regarde, un, homme, avec, téléscope \rbrace$

$P$ :

  • $P ⟶ SN SV$
  • $SN ⟶ Det N \mid Pr \mid SN PP$
  • $Det ⟶ un$
  • $N ⟶ homme \mid télescope$
  • $Pr ⟶ elle$
  • $SV ⟶ V SN \mid V SP$
  • $V ⟶ regarde$
  • $SP ⟶ PP SN$
  • $PP ⟶ avec$
\begin{align*} P & ⟹ SN SV \\ & ⟹ Pr SV \\ & ⟹ elle SV \\ & ⟹ elle V SN \\ & ⟹ elle regarde SN \\ & ⟹ elle regarde SN SP \\ & ⟹ elle regarde Det N SP \\ & ⟹ elle regarde un N SP \\ & ⟹ elle regarde un homme SP \\ & ⟹ elle regarde un homme PP SN \\ & ⟹ elle regarde un homme avec SN \\ & ⟹ elle regarde un homme avec Det N \\ & ⟹ elle regarde un homme avec un N \\ & ⟹ elle regarde un homme avec un télescope \\ \end{align*}
  graph {
    rankdir=TB;
    SN2[label="SN"];
    P -- {SN, SV};
    SN -- Pr;
    Pr -- elle;
    SV -- {V, SN2};
    V -- regarde;
    SN2 -- {Det, N};
  }
Grammaire algébrique linéaire :

grammaire algébrique tq $P⊆N × (𝛴^\ast N 𝛴^\ast ∪ 𝛴^\ast)$

Dérivation gauche (leftmost) :
⟹_{lm} ≝ \lbrace (uA𝛾, u𝛼𝛾) \mid A ⟶ 𝛼∈P, u∈𝛴^\ast, 𝛾∈(𝛴 ∪ N)^\ast \rbrace
Dérivation droite (rigthmost) :
⟹_{rm} ≝ \lbrace (𝛽Av, 𝛽𝛼v) \mid A ⟶ 𝛼∈P, v∈𝛴^\ast, 𝛽∈(𝛴 ∪ N)^\ast \rbrace

NB : L_G(A) = \lbrace w∈𝛴^\ast \mid A ⟹_{lm}^\ast w \rbrace = \lbrace w∈𝛴^\ast \mid A ⟹_{rm}^\ast w \rbrace


Petit soucis :

“Elle regarde (un homme) avec un télescope” ≠ “Elle regarde (un homme avec un télescope)”

⟶ pour cette même phrase, il existe plusieurs arbres de dérivation


Mot $w∈𝛴^\ast$ ambigü :

s’il existe deux arbres de dérivation (/dérivation gauche / dérivation droite) différents pour $w$ dans $G$

Grammaire ambigüe :

s’il existe un mot ambigü dans $L(G)$

NB : la langue naturelle est ambigüe, donc il est souhaitable, pour un grammaire, dans ce cas, de l’être aussi. Mais ce n’est pas le cas pour les langages de programmation.

Ex : expressions arithmétiques

E⟶ E + E \mid E - E \mid E * E \mid (E) \mid n
\begin{align*} E & ⟹ E + E \\ & ⟹ E-E + E \\ & ⟹ n-E + E \\ & ⟹ ⋯ \\ \end{align*}
  graph {
    rankdir=TB;
    plus[label="+"];
    moins[label="-"];
    pd[label=")"];
    pg[label="("];
    E1[label="E"];
    E2[label="E"];
    E3[label="E"];
    E4[label="E"];
    E -- E1;
    E -- plus;
    E -- E2;
    E1 -- n;
    E1 -- moins;
    E1 -- E3;
    E3 -- {pg, E4, pd};
  }

Pour lever les ambiguïtés :

  • on peut parenthéser
  • on donner des règles de priorité ⟶ ce qui est fait en arithmétique

Problème : savoir si une grammaire est ambigüe est indécidable.


Solution possible :

on introduit des termes $T$ et des facteurs $F$ :

E⟶ T \mid T+E \mid T-E \\ T ⟶ F \mid F * T \\ F ⟶ (E) \mid n

Problème : $n-n-n$ est interprété comme $n-(n-n)$

Comme régler ce problème ?

E⟶ T \mid T+E \mid E-T

($E-T$ au lieu de $T-E$)

Récursivité droite :

$E ⟹^+ 𝛼E$, $𝛼∈(N∪𝛴)^\ast$

Récursivité gauche :

$E ⟹^+ E𝛼$, $𝛼∈(N∪𝛴)^\ast$

On a donc utilisé une récursivité gauche pour lever le problème.


Ex: Palindromes pairs

L_{pal} ≝ \lbrace w \widetilde{w} \mid w∈ \lbrace a,b \rbrace^\ast \rbrace
S ⟶ 𝜀 \mid a S a \mid b S b

Langage inhéremment ambigu :

si toute grammaire algébrique qui l’engendre est ambigüe

NB :

  • Savoir s’il existe une autre grammaire non ambigüe ⟶ indécidable
  • Langages réguliers ⟶ jamais inhéremment ambigus, puisqu’en déterminisant l’automate, il n’est plus ambigu.

Formes normales

Ex :

S ⟶ AB \mid aAb \\ A ⟶ Ba \mid Aa \mid a \\ B ⟶ Ca \\ C ⟶ Bc \\ D ⟶ dD \mid d
L(G) ≝ \lbrace a^n b \mid n > 1 \rbrace

En fait, on réduire la grammaire à :

S ⟶ aAb \\ A ⟶ Aa \mid a

Forme réduite

Symbole $X∈N∪𝛴$ accessible
s’il existe $𝛽, 𝛾∈(N∪𝛴)^\ast$ tq $S⟹^\ast 𝛽 X 𝛾$
Symbole $X∈N∪𝛴$ co-accessible
s’il existe $w∈𝛴^\ast$ tq $X⟹^\ast w$

ssi $L(G)≠∅$

Grammaire réduite :

si tous ses symboles (sauf $S$ ? si on n’accepte pas le langage vide) sont accessibles et co-accessibles

taille d’une grammaire $G = ⟨N, 𝛴, P,S⟩$ :

c’est $\vert G \vert ≝ \max(\vert N \vert, \vert 𝛴 \vert, \sum\limits_{A⟶𝛼∈P} (\vert 𝛼 \vert + 1))$

Prop : Soit $G$ une grammaire algébrique.

On peut construire en $O( \vert G \vert)$ une grammaire réduite équivalente

Preuve :

  1. On construit en $O(\vert G \vert)$ une grammaire où tous les symboles (sauf $S$ ?) sont co-accessibles

  2. on élimine les symboles et productions non accessibles.

Pour 2) :

$acc∈N × (N∪𝛴)$ tq $A acc X$ ssi $∃𝛽, 𝛾 ∈ (N∪𝛴)\ast; A ⟹^\ast 𝛽 X 𝛾$

Soit, si $A \leadsto X$ ssi

A ⟶ 𝛼X𝛼' ∈ P, 𝛼,𝛼'∈(N∪𝛴)^\ast

alors $acc = \leadsto^\ast$

Donc l’ens. des symboles accessibles est

acc(S) = \leadsto^\ast(S)
  • Si $G$ est co-accessible, et $A$ est aussi accessible, mq
L_G(A) = L_{G'}(A)

où $G’$ ne contient que les symboles accessibles de $G$.

Soit une dérivation

A ⟹ 𝛼_1 ⟹ ⋯ ⟹ 𝛼_n = w

dans $G$

Par hyp. tous les symboles des $𝛼_i$ sont accessibles (car $A$ est accessible) et co-accessibles.

Donc cette dérivation peut aussi se faire dans $G’$.

Inversement :

A ⟹ 𝛼_1 ⟹ ⋯ ⟹ 𝛼_n = w

dans $G’$, est aussi un dérivation dans $G$.

Réciproquement :

On construit une instance de HORNSAT sur l’ensemble des propositions $N$ signifiant la co-accessibilité du symbole.

Pour toute production

A ⟶ u_0 B_1 u_1 ⋯ u_{n-1} B_n u_n

où $B_1, ⋯, B_n ∈N$ et $u_0, ⋯, u_n ∈𝛴^\ast$

on écrit la clause

A ⟵ B_1 ∧ ⋯ ∧ B_n

Alors $A$ est co-accessible ssi

\lbrace \bot ⟵ A \rbrace ∪ Clauses

est instatisfaisables ?

Donc en temps linéaire ? ⟶ en donnant juste l’ensemble des clauses ⟹ l’algo HORNSAT retourne la valuation minimale ⟶ nous l’ensemble des non-terminaux co-accessibles

Rappel : Pour résoudre HORNSAT positif en temps linéaire :

Algorithme :

Pour toute c = A ⟵ B_1 ∧ ⋯ ∧ B_n ∈ Clauses:
  comptec = n
  Pour 1≤i≤n:
    ajouter c à liste_B_i
  Si n=0:
    S ⟵ S ∪ {A}

Tant que S≠∅:
  S'=∅
  Pour tout B∈S:
    Pour tout c = A ⟵ B_1 ∧ ⋯ ∧ B_n ∈ liste_B tq ¬marque(A):
      comptec -= 1
      si comptec = 0:
        marque(A)
        S' = S'∪{A}
  S = S'

retourner marque(Propositions)

Corollaire : Le problème du vide d’une grammaire algébrique est en temps linéaire (et $PTIME$-complet !)

  • entrée : $G$ grammaire algébrique
  • question : $L(G)≠∅$ ?

Borne sup : se réduit à $S$ co-accessible et donc à une instance de HORNSAT

Borne inf :

  • HORNSAT
  • clôture loi binaire
  • accessibilité graphe “alternant”

se réduisent au problème du vide !

Leave a comment