%% 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


%
%
%

\newlength{\oldparindent}
\oldparindent=\parindent
\renewcommand{\narrower}{\advance\leftskip\oldparindent\advance\rightskip\oldparindent}
\parindent=0pt
\parskip=6ptplus6pt

Les errata suivants sur le document « THL (Théorie des langages) /
Notes de cours » sont relatifs à la version étiquetée
\verb=28531fc Thu Jan 23 14:37:46 2020 +0100=
et distribuée pour l'année universitaire 2020–2021.

\medskip

Dans la démonstration de la proposition 3.2.4, qui constitue la
construction de l'automate de Glushkov d'une concaténation, la
construction donnée affirme à tort que les états finaux de l'automate
construit sont uniquement ceux du second automate ($A_2$) concaténé.
Or il faut aussi marquer comme finaux les états finaux de $A_1$
\emph{lorsque (et seulement lorsque)} l'état initial $q_2$ de $A_2$
était final.

Pour corriger cette erreur, ajouter à la fin de la phrase (page 32,
lignes 11–13)

{\narrower

L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant
que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant
chaque transition sortant de $q_2$ par une transition identiquement
étiquetée, et de même cible, partant de \emph{chaque} état final
de $A_1$.

\par}

la parenthèse suivante

{\narrower

(ces derniers seront marqués finaux si $q_2$ était final dans $A_2$)

\par}

et remplacer la phrase (page 32, lignes 15–18)

{\narrower

On définit alors l'automate $A'$ dont l'ensemble d'états est $Q'$,
l'état initial est $q_1$, les états finaux $F' = F_2$, et la relation
de transition $\delta$ est la réunion de $\delta_1$, de l'ensemble des
triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$, et enfin de
l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q') \in \delta_2$
et que $q\in F_1$.

\par}

par

{\narrower

On définit alors l'automate $A'$ dont l'ensemble d'états est $Q'$,
l'état initial est $q_1$, l'ensemble $F'$ des états finaux est $F_2$
si $q_2$ n'était pas final dans $A_2$ et $F_1 \cup F_2$ si $q_2$ était
final dans $A_2$, la relation de transition $\delta'$ est la réunion
de $\delta_1$, de l'ensemble des triplets $(q,x,q') \in \delta_2$ tels
que $q\neq q_2$, et enfin de l'ensemble des triplets $(q,x,q')$ tels
que $(q_2,x,q') \in \delta_2$ et que $q\in F_1$.

\par}

On notera que, en revanche, la remarque qui suit la démonstration, et
qui décrit une façon de voir la construction en passant par l'ajout
temporaire de transitions spontanées, est correcte (l'élimination des
transitions spontanées en question conduira à rendre finaux les états
de $A_1$ lorsque $q_2$ l'état), et est probablement la façon la plus
simple de mémoriser cette construction sans se tromper.

\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}

\medskip

Dans la démonstration de la proposition 3.4.7, qui constitue la
procédure d'élimination des états, il n'est pas suffisamment clair
quelles sont les paires d'états concernées par l'élimination de
l'état $q$.  Pour remédier à ce manque de clarté, ajouter une note en
bas de page après « simultanément pour toute paire » (page 40,
ligne 14 en partant du bas) :

{\narrower

Plutôt qu'examiner toutes les paires, on peut se contenter d'examiner
les cas où \emph{soit} il existe une transition de $q_1$ vers $q_2$
\emph{soit} il existe à la fois une transition de $q_1$ vers $q$ et
une transition de $q$ vers $q_2$.  En revanche, insistons bien sur le
fait que le cas où $q_1$ et $q_2$ coïncide doit être traité comme les
autres.

\par}

\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}

\medskip

Paragraphe 2.1.7, l'expression rationnelle donnée entre parenthèses
comporte une faute de frappe : page 18, ligne 9 en partant du bas,
remplacer $(b|c){*}a(b|c){*}b(a|b|c){*}$ par
$(b|c){*}a(a|c){*}b(a|b|c){*}$.

\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}

\medskip

Paragraphe 4.3.2, la grammaire ne devrait pas avoir de
production $\varepsilon$ compte tenu de ce qui en est dit
en-dessous  : page 56, ligne 18, remplacer $S \rightarrow U \;|\; V
\;|\; \varepsilon$ par $S \rightarrow U \;|\; V$.

\hbox to\hsize{\hfill\hbox to4cm{\hrulefill}\hfill}

\medskip

Paragraphe 4.3.5, il manque à la grammaire $G'$ des productions $U
\rightarrow \varepsilon$ et $V \rightarrow \varepsilon$ : page 58,
lignes 4–5, remplacer
\[
\begin{aligned}
U &\rightarrow aUbU\\
V &\rightarrow bVaV\\
\end{aligned}
\]
par
\[
\begin{aligned}
U &\rightarrow aUbU \;|\; \varepsilon\\
V &\rightarrow bVaV \;|\; \varepsilon\\
\end{aligned}
\]



%
%
%
\end{document}