fiche

Définitions

Grammaire

\(G = (V,\Sigma,R,S)\)
où \(V\) est l’ensemble de variables, \(\Sigma\) l’alphabet, \(R\) les règles de production, et S l’axiome ou variable de départ

Grammaire hors contexte

On limite les règles de la grammaires à \(V \times (\Sigma \cup V)^{\ast}\)

Grammaire linéaire

Règles de la forme \(V \times \left( \Sigma^{\ast}V\Sigma^{\ast} \cup \Sigma^{\ast} \right)\)
L’ensemble des langages engendré par des grammaires linéaires est noté \(\text{Lin}\left( \Sigma^{\ast} \right)\)

Grammaire régulière

Grammaire linéaire droite (ie \(R \subset V \times \left( \Sigma^{\ast}V \cup \Sigma^{\ast} \right)\))
L’ensemble des langages engendré par des grammaires régulières est noté \(\text{Reg}\left( \Sigma^{\ast} \right)\)

Grammaire ambigue

Une grammaire est ambigue si un mot possède deux dérivations différentes

Langage inhéremment ambigu

Un langage est ambigu si toutes les grammaires qui l’engendrent sont ambigues

Langages hors contexte

L’ensemble des langages engendrés par des grammaires hors contexte. Il est noté \(\text{HC}\left( \Sigma^{\ast} \right)\)

Remarque: \(\text{Reg}\left( \Sigma^{\ast} \right) \subset \text{ Lin}\left( \Sigma^{\ast} \right) \subset \text{ HC}\left( \Sigma^{\ast} \right)\)

Automate à pile

\(\mathcal{A} = \left( Q,\Sigma^{\ast},Z,\Gamma,\left( q_{0},z_{0} \right),K \right)\)
où:

• \(Q\) est un ensemble fini d’états,

• \(\Sigma\) est l’alphabet d’entrée,

• \(Z\) est l’alphabet de pile,

• \(\left( q_{0},z_{0} \right) \in Q \times Z\) est la configuration initiale,

• \(T \subset \left( \left( Q \times Z \times \left( \Sigma \cup \left\{ \varepsilon \right\} \right) \right) \times \left( Q \times Z^{\ast} \right) \right)\) est la relation de transition,

• \(K \subset Q \times Z^{\ast}\) est une condition d’acceptation.

Les modes d’acceptation sont:

• Par pile vide

• Par état final

• Par pile vide et état final

Remarque: dans tous les cas le mots doit avoir été lu jusqu’à la fin

Automate à pile déterministe

On a \(\mathcal{A} = \left( Q,\Sigma^{\ast},Z,\Gamma,\left( q_{0},z_{0} \right),K \right)\)

• Pas deux transition avec la même étiquette depuis un même état

• S’il y a une \(\varepsilon\)-transition provenant d’un état, aucune autre étiquette

L’ensemble des langages engendré par des Automate à pile déterministe est noté \(\text{DHC}\left( \Sigma^{\ast} \right)\)

Théorème: Soit \(L \in \text{ DHC}\left( \Sigma^{\ast} \right)\). Alors \(L\) peut être engendré par une grammaire non ambigüe

Remarque: on a \(\text{Reg}\left( \Sigma^{\ast} \right) \subsetneq \text{ DHC}\left( \Sigma^{\ast} \right) \subsetneq \text{ HC}\left( \Sigma^{\ast} \right)\)

Symbole utile / productif

Un symbole \(X \in V\) est utile s’il existe un mot \(w \in \Sigma^{\ast}\) tel que
\(\alpha X\beta \Rightarrow^{\ast}w\text{ avec }\alpha,\beta \in (\Sigma \cup V)^{\ast}\)

Grammaire réduite

Une grammaire est dite réduite si elle ne comporte au symbole non utile

Symbole accessible

Un symbole \(X \in V\) est accessible s’il existe une dérivation \(S \Rightarrow^{\ast}\alpha X\beta\)

Grammaire propre

Une grammaire est propre si elle ne contient pas de production unitaire ni d’\(\varepsilon\)-production

Méthodes

Stabilité des ensembles:

Langage reconnaissable

Si \(L_{1},L_{2} \subset A^{\ast}\) sont reconnaissables, alors:

• \(\overline{L_{1}}\) est reconnaissable

• \(L_{1} \cup L_{2},L_{1} \cap L_{2}\) sont reconnaissables

• \(L_{1} \cdot L_{2}\) est reconnaissable

• \(L_{1}^{+},L_{2}^{\ast}\) sont reconnaissables

Langage HC

Si \(L_{1},L_{2} \subset A^{\ast}\) sont HC et \(K \subset A^{\ast}\) est reconnaissable, alors:

• \(L_{1} \cup L_{2}\) est HC

• \(L_{1} \cap K\) est reconnaissable

• \(L_{1}^{\ast}\) est HC

• si \(L_{1}\) est deterministe, \(\overline{L_{1}}\) est reconnaissable

Lemme fondamental

Soit \(G = (V,\Sigma,R,S)\) une grammaire hors-contexte, soit \(k \in {\mathbb{N}}\) et \(\alpha_{1},\alpha_{2},\beta \in (\Sigma \cup V)^{\ast}\) . Si \(\alpha_{1}\alpha_{2} \Rightarrow^{k}\beta\), alors il existe \(\beta_{1},\beta_{2} \in (\Sigma \cup V)^{\ast}\) et \(k_{1},k_{2} \in {\mathbb{N}}\) tel que \(\beta = \beta_{1}\beta_{2},\alpha_{1} \Rightarrow_{1}^{k}\beta_{1},\alpha_{1} \Rightarrow_{1}^{k}\beta_{2}\text{ et }k_{1} + k_{2} = k\)

Transformation automate \(\rightarrow\) grammaire

On note toutes les transitions sous forme \(A \rightarrow \left\lbrack q_{i}Zq_{j} \right\rbrack\) (\(\left\lbrack q_{i}Zq_{j} \right\rbrack\) sera par la suite remplacé par des variables)

Identifier règles qui pop et qui push
on met d’abord les pop, qui sont plus simples:
\(\left\lbrack \text{etat\_debut }\text{ symbole\_pile }\text{ etat\_arrive} \right\rbrack \rightarrow \text{ lettre\_a\_pop}\)

Puis les push:
\(\left\lbrack \text{etat\_debut }\text{ symbole\_pile }\text{ etat\_arrive} \right\rbrack \rightarrow \text{ lettre\_a\_empiler }\left\lbrack \text{circuit à prendre pour dépiler règles de droite} \right\rbrack\)

Transformation grammaire \(\rightarrow\) automate

\(\begin{array}{r} \left( q_{0},Z_{0} \right)\overset{\varepsilon}{\rightarrow}\left( q_{l},SZ_{0} \right) \\ \left( q_{0},X \right)\overset{\varepsilon}{\rightarrow}\left( q_{l},w \right),\forall X \rightarrow w \in R \\ \left( q_{0},a \right)\overset{a}{\rightarrow}\left( q_{l},\varepsilon \right),\forall a \in \Sigma \\ \left( q_{l},Z_{0} \right)\overset{\varepsilon}{\rightarrow}\left( q_{f},\varepsilon \right) \end{array}\)

Déterminer si un langage est reconnaissable

Faire hypothèse:

• Reconnaissable? \(\rightarrow\) contruction d’automate / regex

• Non reconnaissable? \(\rightarrow\) raisonnement par l’absurde avec: règles de cloture et lemme de l’étoile

Lemme de l’étoile

Soit \(L\) un langage reconnaissable. Soit \(w = xyz \in L\). Alors il existe \(N \in {\mathbb{N}},|w| \geq N\) et:

• \(|y| > 0\)

• \(|xy| \leq N\)

• \(xy^{\ast}z \in L\)

Démo: \(L = \left\{ a^{p}~|~p\text{ premier} \right\}\) non reconnaissable

Supposons qu’il l’est.
On dispose de \(N\) tq \(\forall\omega \in L\) si \(|\omega| \geq N\) alors on respecte les hypo du lemme de l’étoile
Soit \(P\) premier tq \(P \geq N,\omega = a^{P}\) On décompose P en trois nombres: \(P = p + q + r\). Alors
\(\omega = a^{p}a^{q}a^{r} = xyz\)

On pose \(m = p + 2q + r + 2\) D’après le lemme de l’étoile, \[xy^{m}z = a^{p + r + q(p + 2q + r + 2)} = a^{(q + 1)(p + 2q + r)} \in L\] or \((q + 1)(p + 2q + r)\) n’est pas premier, contradiction

Déterminer si un langage est hors contexte

Faire hypothèse:

• hors contexte? \(\rightarrow\) contruction d’automate / regex

• Non hors contexte? \(\rightarrow\) raisonnement par l’absurde avec le lemme d’itération algébrique

Lemme d’itération algébrique

Soit \(L \in \text{ HC}\left( \Sigma^{\ast} \right)\). Alors il existe \(N \in {\mathbb{N}}\) tel que: \(\forall\omega \in L\) si \(|\omega| > N\) alors \(w = uvxyz\), avec:

• \(|vy| > 0\)

• \(|vxy| \leq N\)

• \(uv^{i}xy^{i}z \in L,\forall i \in {\mathbb{N}}\)

Démo: \(L = \{ a^{n}b^{m}c^{n}d^{m}\)} n’est pas HC

Supposons \(L\) HC. On considère \(\omega = a^{N}b^{N}c^{N}d^{N}\) \(|\omega| \geq N\)

On définit 4 blocs consécutifs de longueur N: \(A = a^{n},\ldots\)

Comme \(|vxy| \leq N\), \(vxy\) est:

• soit dans un seul bloc

• soit en chevauche

1. Si \(vxy \in A\) D’après le lemme de l’étoile, \(uv^{0}xy^{0}z \in L\) or le nombre de c est constant, alors que le nombre de a diminue. On a \(n = |w|_{a} < |w|_{c} = n\). Absurde

2. Si \(vxy\) chevauche \(AB\) Donc v et y contiennent soit des a soit des b S’il contient au moins un a: cas 1 S’il contient au moins un b: cas 1 en miroir

Réduction de grammaires

\(G' = \mathcal{R}(\mathcal{P}(G))\)

Elimination des symboles non-productifs

On calcule \({\mathbb{P}}(G)\) l’ensemble des symboles accessibles. Construction récursive de \({\mathbb{P}}(G)\): \[\begin{aligned} & P_{0}(G) = \left\{ X~|~X \rightarrow w \in R\text{ avec }w \in \Sigma^{\ast} \right\} \\ & P_{n + 1}(G) = P_{n}(G) \cup \left\{ X~|~W \rightarrow u \in R\text{ et }u \in \left( \Sigma \cup P_{n}(G) \right)^{\ast} \right\} \\ & {\mathbb{P}}(G) = \bigcup P_{n}(G) \end{aligned}\]

On calcule alors \(\mathcal{P}(G)\) en retirant à \(G\) toutes les productions ne contenant ni à gauche ni à droite un élément de \({\mathbb{P}}(G)\)

Elimination des symboles non-accessibles

On calcule \({\mathbb{R}}(G)\) l’ensemble des symboles accessibles. Construction récursive de \({\mathbb{R}}(G)\): \[\begin{aligned} & R_{0}(G) = \left\{ S \right\} \\ & R_{n + 1}(G) = R_{n}(G) \cup \left\{ X~|~Y \rightarrow u \in R\text{ et }Y \in R_{n}(G)\text{ et }X \in u \right\} \\ & {\mathbb{R}}(G) = \bigcup R_{n}(G) \end{aligned}\]

On calcule alors \(\mathcal{R}(G)\) en retirant à \(G\) toutes les productions ne contenant ni à gauche ni à droite un élément de \({\mathbb{R}}(G)\)

Rendre une grammaire propre

Il faut la laver
Trouver toutes \(\varepsilon\)-production, les supprimer, créer des nouvelles règles exprimant toutes les possibilité de l’absence de ce symbole.
Par la suite, supprimer les mono-production avec en remplaçant leurs expressions par l’expension de la variable complète

Page incomplète ou erronée? Contribuez sur le repo