path: root/errata-notes-inf105.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[a4paper,twoside,inner=2.75cm,outer=2.25cm,vmargin=3cm]{geometry}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
%\usepackage{tikz}
%\usetikzlibrary{arrows,automata,positioning,calc}
%
\newcommand{\limp}{\mathrel{\Longrightarrow}\relax}
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
\DeclareUnicodeCharacter{0101}{\=a}
\DeclareUnicodeCharacter{1E47}{\d{n}}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\defin}[2][]{\def\latexsucks{#1}\ifx\latexsucks\empty\index{#2}\else\index{\latexsucks}\fi\textbf{#2}}
%
%
%
\begin{document}
\title{THL (Théorie des langages)\\Notes de cours : errata}
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pretolerance=8000
\tolerance=50000
\linepenalty=5  % Default is supposedly 10

\vskip1cm


%
%
%

Les errata suivants sur le document « THL (Théorie des langages) /
Notes de cours » sont relatifs à la version étiquetée
\verb=f1826f0 Tue Nov 14 13:05:17 2017 +0100=
et distribuée pour l'année universitaire 2017–2018.

\medskip

¶1.2.6, dernier paragraphe, (page 5), l'affirmation « Le suffixe
correspondant au préfixe $abb$ est $bcab$ puisque $abbcab =
(abb)(bcab)$ » est incorrecte, il faut remplacer $bcab$ par $cab$ et
lire : « Le suffixe correspondant au préfixe $abb$ est $cab$ puisque
$abbcab = (abb)(cab)$ ».

\medskip

{\footnotesize

¶1.5.3, dernier paragraphe, (page 14), au lieu de « racourcis », lire
« raccourcis ».

\medskip

Démonstration de la proposition 2.4.6, deuxième paragraphe, (page 27),
dans la phrase « on crée une transition $q\to q'$ étiquetée par $x$ »,
la précision que $x \in \Sigma$ peut être utile : remplacer par « on
crée une transition $q\to q'$ étiquetée par $x \in \Sigma$ ».

\par}

\medskip

Démonstration du lemme 3.2.2, deuxième paragraphe, (page 30), le
traitement des états finaux de l'automate $A'$ construit n'est pas
correct, il faut marquer le nouvel état $q_0$ créé comme final
lorsqu'il existait un état initial qui était aussi final.  En
conséquence, remplacer les $F$ de ce paragraphe par $F'$, retirer le
mot « et » devant « $\delta'$ est la réunion », et ajouter à la fin du
paragraphe : « et enfin $F' = F$ ou $F' = F\cup\{q_0\}$ selon que
$I\cap F = \varnothing$ ou $I\cap F \neq \varnothing$ respectivement
(i.e., $q_0$ est final lorsqu'il existait déjà un état à la fois
initial et final) ».  Le paragraphe ainsi modifié est le suivant :

{\smallskip

Formellement : soit $A = (Q,I,F,\delta)$.  On définit alors $A' =
(Q',\{q_0\},F',\delta')$ de la manière suivante : $Q' = Q \uplus
\{q_0\}$ (où $\uplus$ désigne une réunion disjointe), $\delta'$ est la
réunion de l'ensemble des transitions $(q,x,q')$ qui étaient déjà
dans $\delta$ et de l'ensemble des $(q_0,x,q')$ telles qu'il existe
une transition $(q,x,q') \in \delta$ avec $q\in I$, et enfin $F' = F$
ou $F' = F\cup\{q_0\}$ selon que $I\cap F = \varnothing$ ou $I\cap F
\neq \varnothing$ respectivement (i.e., $q_0$ est final lorsqu'il
existait déjà un état à la fois initial et final).

\par}

\medskip

{\footnotesize

¶3.6.3 (page 56), au lieu de « fącon », lire « façon ».

\medskip

¶4.0.1 (page 50), au lieu de « démarré », lire « démarrée ».

\medskip

¶4.1.7, second paragraphe, (page 53), pour alléger la syntaxe,
déplacer la parenthèse commençant par « plus le numéro du type » à la
fin du paragraphe : « 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 4.2.2 ci-dessous, forment une hiérarchie
appelée 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. ».

\medskip

¶4.2.4, deuxième paragraphe, (page 55), au lieu de « racourci », lire
« raccourci ».

\par}

\medskip

¶4.4.1 (page 58), la rédaction ne rend pas suffisamment explicite le
fait que tout nœud qui n'est pas une feuille doit être étiqueté par un
nonterminal.  Pour rendre ce fait plus explicite, remplacer dans le
deuxième tiret « si un nœud de l'arbre est étiqueté par $T$ et n'est
pas une feuille (i.e., s'il a des fils) » par « si un nœud de l'arbre
n'est pas une feuille (i.e., s'il a des fils) et si on appelle $T$ son
étiquette », et ajouter après les deux sous-cas de ce tiret
(c'est-à-dire après « dans $G$ », en passant à la ligne) la
parenthèse : « 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$ ».
Le passage ainsi modifié est le suivant :

{\smallskip

Soit $G$ une grammaire hors contexte sur un alphabet $\Sigma$ et $N$
l'ensemble de ses nonterminaux.  Un \textbf{arbre d'analyse} (ou
\textbf{arbre de dérivation} ; en anglais \textbf{parse tree})
\textbf{incomplet} pour $G$ est un arbre (fini, enraciné et ordonné)
dont les nœuds sont étiquetés par des éléments de $\Sigma \cup N \cup
\{\varepsilon\}$, vérifiant les propriétés suivantes :
\begin{itemize}
\item la racine de l'arbre est étiquetée par l'axiome $S$ de $G$ ;
\item si un nœud de l'arbre n'est pas une feuille (i.e., s'il a des
  fils) et si on appelle $T$ son étiquette, alors
\begin{itemize}
\item soit ce nœud a un unique fils étiqueté $\varepsilon$ et il
  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$,
\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}

\par}

\medskip

¶4.5.2, avant-dernier paragraphe (en-dessous des arbres, page 61),
l'affirmation « Cette grammaire n'est donc pas ambiguë » est
incorrecte.  Lire à la place : « Cette grammaire est donc ambiguë ».

\medskip

{\footnotesize

¶4.7.5, dernier paragraphe, (page 66), au lieu de « complexitée »,
lire « complexité ».

\smallskip

¶4.7.6, premier paragraphe, (page 66), au lieu de « meme », lire
« même ».

\par}

\medskip

Définition 5.1.5, premier paragraphe, (page 70), retirer la parenthèse
« (fonction) » après « calculable » (qui était destinée à l'index
uniquement).

\medskip

{\footnotesize

Définiiton 5.1.5, deuxième paragraphe, (page 66), pour éclaircir la
syntaxe, ajouter « et » devant « « non » ($0$) ».

\medskip

¶5.1.10 (page 72), il manque « comme » avant le dernier mot :
remplacer « donne bien le résultat final de $T$ résultat » par « donne
bien le résultat final de $T$ comme résultat ».

\medskip

¶5.2.1, note en bas de page 28, (page 73), retirer la virgule après
« Java ».

\medskip

Démonstration du théorème 5.2.4, premier paragraphe, (page 74),
remplacer « on n'a pas de choix que de ne pas terminer » par « la
seule possibilité est de ne pas terminer ».

\medskip

Démonstration du théorème 5.2.4, deuxième paragraphe, (page 74), pour
éclaircir la syntaxe, ajouter « et ensuite » devant « (2º) ».

\par}

%
%
%
\end{document}