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)
- 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$
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 :
-
On construit en $O(\vert G \vert)$ une grammaire où tous les symboles (sauf $S$ ?) sont co-accessibles
-
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
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