summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex23
1 files changed, 13 insertions, 10 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 852c98a..0cf4d2a 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1199,7 +1199,7 @@ ASCII/Unicode\footnote{...ou parfois l'ordre de tri défini par la
ni} \texttt{a} ni \texttt{e} ni\texttt{i} ni entre \texttt{o}
et \texttt{z}).
-Toutes sortes d'autres racourcis ou commodités de notation peuvent
+Toutes sortes d'autres raccourcis ou commodités de notation peuvent
exister, par exemple \texttt{\char"5C<} et \texttt{\char"5C>} pour
désigner un début et une fin de mot (la définition précise de « mot »
pouvant varier), ou encore \texttt{$r$\{$n_1$,$n_2$\}} qui cherche
@@ -4487,7 +4487,7 @@ principal intérêt de définir des \emph{syntaxes structurées}, par
exemple la syntaxe d'un langage informatique (typiquement un langage
de programmation). En fait, l'étude des grammaires formelles en
général, et des grammaires hors contexte en particulier, a été
-démarré\footnote{Certains font remonter leur origine bien plus loin :
+démarrée\footnote{Certains font remonter leur origine bien plus loin :
on peut trouver une forme de grammaire hors contexte dans la manière
dont l'Indien Pāṇini (probablement au IV\textsuperscript{e} siècle
av. notre ère) décrit la grammaire du sanskrit.} en 1956 par le
@@ -4779,10 +4779,10 @@ remplacement à partir de l'axiome.
Les grammaires de types 0 et 1, avec celles de type 2 c'est-à-dire
hors contexte, et celles de type 3 (= régulières) qui seront définies
-en \ref{regular-grammar} ci-dessous, forment une hiérarchie (plus le
+en \ref{regular-grammar} ci-dessous, forment une hiérarchie appelée
+\defin[Chomsky (hiérarchie de)]{hiérarchie de Chomsky} : plus le
numéro du type est élevé plus la grammaire est contrainte et plus la
-classe de langages définie est petite) appelée \defin[Chomsky
- (hiérarchie de)]{hiérarchie de Chomsky}.
+classe de langages définie est petite.
\subsection{Langages rationnels et algébriques, stabilité}
@@ -4903,7 +4903,7 @@ des règles d'une grammaire, d'écrire $T \rightarrow \alpha_1 | \cdots
\rightarrow \alpha_1$ jusqu'à $T \rightarrow \alpha_n$. Par exemple,
la grammaire présentée en \ref{basic-example-context-free-grammar}
peut s'écrire $S \rightarrow aSb | \varepsilon$. Il s'agit d'un
-simple racourci d'écriture (comparer avec une convention semblable
+simple raccourci d'écriture (comparer avec une convention semblable
faite pour les automates en \ref{graphical-representation-of-dfa}).
{\footnotesize
@@ -5179,8 +5179,11 @@ suivantes :
existe une règle $T \rightarrow \varepsilon$ dans $G$,
\item soit ce nœud a des fils étiquetés par des éléments $x_1\cdots
x_n$ (où $n\geq 1$) de $\Sigma \cup N$ et il existe une règle $T
- \rightarrow x_1\cdots x_n$ dans $G$.
+ \rightarrow x_1\cdots x_n$ dans $G$,
\end{itemize}
+(dans ces deux sous-cas, il résulte de l'existence d'une règle
+$T\rightarrow\cdots$ que $T$ est un nonterminal : seules les feuilles
+peuvent être étiquetées par un terminal ou $\varepsilon$).
\end{itemize}
\smallskip
@@ -5447,7 +5450,7 @@ mais aussi
%%% end parsetree2b %%%
\end{center}
-Cette grammaire n'est donc pas ambiguë. Remarquons que le langage
+Cette grammaire est donc ambiguë. Remarquons que le langage
qu'elle engendre est $\{a\}^+ = \{a^n : n\geq 1\}$ (car il est évident
que tout mot engendré par la grammaire est dans $\{a\}^+$, et
réciproquement il est facile de fabriquer une dérivation de $a^n$ pour
@@ -5865,7 +5868,7 @@ L'algorithme qu'on vient de décrire (pour tester si $w \in L(G')$ une
fois $G'$ sous forme normale de Chomsky) porte le nom
d'\defin[Cocke-Younger-Kasami (algorithme de)]{algorithme de
Cocke–Younger–Kasami} ou algorithme \index{CYK (algorithme
- de)|see{Cocke-Younger-Kasami}}\textbf{CYK}. Sa complexitée est
+ de)|see{Cocke-Younger-Kasami}}\textbf{CYK}. Sa complexité est
cubique en la longueur de $w$.
\par}
@@ -6420,7 +6423,7 @@ d'un tel $k$).
étapes de $T$ termine toujours (c'est bien l'intérêt), et (B) si
l'algorithme $T$ termine effectivement, alors pour $m$ suffisamment
grand, exécuter au plus $m$ étapes donne bien le résultat final
- de $T$ résultat.\par}
+ de $T$ comme résultat.\par}
{\footnotesize\thingy\textbf{Complément/exercice :} Un ensemble $A
\subseteq \mathbb{N}$ infini est décidable si et seulement si il