%% 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 )n-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}