diff options
| -rw-r--r-- | notes-inf105.tex | 23 |
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 |