summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex9
1 files changed, 4 insertions, 5 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 2d7c3e8..bdaa2bd 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3236,10 +3236,7 @@ simplement $\{a\}^* = \{a^i : i\in\mathbb{N}\}$ ; et le langage
$L(G,T)$ est $\{a^j b^j : j\in\mathbb{N}\}$ comme
en \ref{basic-example-context-free-grammar}. Le langage $L(G) =
L(G,A)\, L(G,T)$ est donc $\{a^i b^j : i \geq j\}$, l'ensemble des
-mots de la forme $a^i b^j$ pour lesquels $i \geq j$. (Ce langage est
-intéressant sur le plan théorique, car bien qu'il soit algébrique et
-ici défini par une grammaire inambiguë, il ne peut pas être analysé
-par un analyseur LL.)
+mots de la forme $a^i b^j$ pour lesquels $i \geq j$.
On peut aussi considérer la grammaire $G'$ définie par
\[
@@ -3250,7 +3247,9 @@ T &\rightarrow aTb \;|\; \varepsilon\\
\]
Il n'est pas difficile de se convaincre qu'elle engendre le même
langage $L(G)$ que la précédente (elle est donc faiblement équivalente
-à $G$).
+à $G$). (Ce langage est intéressant sur le plan théorique, car bien
+qu'il soit algébrique et ici défini par une grammaire inambiguë, il ne
+peut pas être analysé par un analyseur LL.)
\thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire
(d'axiome $S$)