summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-14 14:13:10 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-11-14 14:15:41 (GMT)
commit0eca47be5d745d3bd21733a2a88c032d6869989d (patch)
tree1fea67ddcae1155ef3c09a2a286a4542c90142f3
parent2d0fa90132f68fbc18834cc062fb2137f70add5b (diff)
downloadinf105-0eca47be5d745d3bd21733a2a88c032d6869989d.zip
inf105-0eca47be5d745d3bd21733a2a88c032d6869989d.tar.gz
inf105-0eca47be5d745d3bd21733a2a88c032d6869989d.tar.bz2
Start defining DFAs, and give a first example (typeset with dot2tex + TikZ).
-rw-r--r--figs/example1.dot11
-rw-r--r--notes-inf105.tex99
2 files changed, 101 insertions, 9 deletions
diff --git a/figs/example1.dot b/figs/example1.dot
new file mode 100644
index 0000000..60873a6
--- /dev/null
+++ b/figs/example1.dot
@@ -0,0 +1,11 @@
+digraph example1 {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial",label="0"];
+ q1 [style="state,final",label="1"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q0 [label="a"];
+ q1 -> q1 [label="a"];
+ q0 -> q1 [label="b"];
+ q1 -> q0 [label="b"];
+}
diff --git a/notes-inf105.tex b/notes-inf105.tex
index d1e43da..1efcf60 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -18,7 +18,7 @@
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
-\usetikzlibrary{matrix}
+\usetikzlibrary{arrows,automata,positioning}
\usepackage[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
@@ -33,7 +33,6 @@
\newtheorem{scho}[comcnt]{Scholie}
\newtheorem{algo}[comcnt]{Algorithme}
\renewcommand{\qedsymbol}{\smiley}
-\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
@@ -52,6 +51,13 @@
\hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
%
+% NOTE: compile dot files with
+% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex
+\tikzstyle{automaton}=[>=stealth',initial text={}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
%
\begin{document}
\title{THL (Théorie des langages)\\Notes de cours \textcolor{red}{provisoires}}
@@ -521,13 +527,14 @@ Le mot vide appartient toujours à $L^*$ (quel que soit $L$) puisque
$L^0 = \{\varepsilon\}$ et qu'on peut prendre $r=0$ ci-dessus
(autrement dit, le mot vide est la concaténation de zéro mots de $L$).
-On introduit parfois la notation $L^+ = \bigcup_{r=1}^{+\infty} L^r =
-\{w_1\cdots w_r : r>0,\penalty-100\, w_1,\ldots,w_r\in L\}$ pour
-l'ensemble des mots formés par concaténation d'un nombre \emph{non
- nul} de mots de $L$. Lorsque le mot vide $\varepsilon$ n'appartient
-pas déjà à $L$, ce langage $L^+$ diffère de $L^*$ seulement en ce
-qu'il ne contient pas $\varepsilon$ ; tandis que si $\varepsilon$
-appartient déjà à $L$, alors $L^+$ est égal à $L^*$.
+\thingy\label{kleene-plus} On introduit parfois la notation $L^+ =
+\bigcup_{r=1}^{+\infty} L^r = \{w_1\cdots w_r : r>0,\penalty-100\,
+w_1,\ldots,w_r\in L\}$ pour l'ensemble des mots formés par
+concaténation d'un nombre \emph{non nul} de mots de $L$. Lorsque le
+mot vide $\varepsilon$ n'appartient pas déjà à $L$, ce langage $L^+$
+diffère de $L^*$ seulement en ce qu'il ne contient pas $\varepsilon$ ;
+tandis que si $\varepsilon$ appartient déjà à $L$, alors $L^+$ est
+égal à $L^*$. En toute généralité, on a $L^+ = LL^*$.
\subsection{Langages rationnels et expressions rationnelles}
@@ -668,6 +675,80 @@ $(ab|cd)$ et pas comme $a(b|c)d$).
vraie lettre et non pas du mot vide ; on peut ignorer cette
subtilité qui n'a que très peu d'importance).\par}
+La barre de disjonction que nous avons notée ${|}$ est souvent plutôt
+notée $+$ par les mathématiciens. Il y a ici un risque de confusion
+lié au fait que, en informatique, le symbole \texttt{+} est utilisé
+par de nombreux moteurs d'expressions régulières (par exemple,
+\texttt{egrep}) pour désigner l'opération évoquée en \ref{kleene-plus}
+(de sorte que $r+$ a le même sens que $rr*$).
+
+
+\section{Automates finis}
+
+\setcounter{comcnt}{0}
+
+\thingy Les automates finis sont un modèle de calcul particulièrement
+simple et particulièrement appropriés à l'étude et à l'analyse des
+langages rationnels. Il faut imaginer un automate fini comme une
+machine disposant d'une quantité finie (et sous-entendu, très limitée)
+de mémoire : la configuration complète de cette mémoire est décrite
+par un \emph{état}, qui appartient à un ensemble fini d'états
+possibles. L'automate prendra une décision (passer dans un nouvel
+état) en fonction de son état actuel et de la lettre qu'on lui donne à
+consommer.
+
+\subsection{Automates finis déterministes (=DFA)}
+
+\thingy Un \textbf{automate fini déterministe}, ou en abrégé
+\textbf{DFA} (pour \textit{deterministic finite automaton}) sur un
+alphabet $\Sigma$ est la donnée
+\begin{itemize}
+\item d'un ensemble fini $Q$ dont les éléments sont appelés
+ \textbf{états},
+\item d'un état $q_0 \in Q$ appelé \textbf{état initial},
+\item d'un ensemble $F \subseteq Q$ d'états appelés états
+ \textbf{finaux}\footnote{Le pluriel de « final » est indifféremment
+ « finaux » ou « finals ».} ou \textbf{acceptants},
+\item d'une fonction $\delta \colon Q\times\Sigma \to Q$ appelée
+ \textbf{fonction de transition}.
+\end{itemize}
+
+Graphiquement, on représente un DFA comme un graphe orienté aux arêtes
+étiquetées par des éléments de $\Sigma$ : plus exactement, on trace un
+nœud pour chaque élément $q \in Q$, et lorsque $\delta(q,x) = q'$ on
+introduit une arête $q \to q'$ étiquetée par la lettre $x$. La
+condition sur $\delta$ (pour être un DFA) est alors que, pour chaque
+état $q \in Q$ et chaque lettre $x \in \Sigma$, il existe une unique
+arête partant de $q$ et étiquetée par $x$. En outre, on introduit une
+arête pointant de nulle part vers $q_0$, et pour chaque $q\in F$ une
+arête pointant de $q$ vers nulle part\footnote{Certains auteurs
+ préfèrent d'autres conventions, par exemple celle consistant à
+ entourer deux fois les états finaux.}.
+
+\thingy Pour donner un exemple simple, l'automate sur $\Sigma =
+\{a,b\}$ représenté ci-dessous a $Q = \{0,1\}$ et $q_0 = 0$ et $F =
+\{1\}$ et la fonction de transition $\delta$ donnée par $\delta(0,a) =
+0$ et $\delta(0,b) = 1$ et $\delta(1,a) = 1$ et $\delta(1,b) = 0$. On
+pourra se convaincre (une fois lues les définitions plus loin) que cet
+automate accepte les mots dont le nombre de $b$ est pair.
+
+\begin{center}
+%%% begin example1 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (98bp,20.306bp) [draw,circle,state,final] {$1$};
+ \node (q0) at (18bp,20.306bp) [draw,circle,state,initial] {$0$};
+ \draw [->] (q1) ..controls (75.212bp,3.6347bp) and (64.284bp,-1.3057bp) .. (54bp,1.3057bp) .. controls (50.042bp,2.3107bp) and (46.047bp,3.8633bp) .. node[auto] {$b$} (q0);
+ \draw [->] (q0) ..controls (46.106bp,20.306bp) and (58.578bp,20.306bp) .. node[auto] {$b$} (q1);
+ \draw [->] (q1) ..controls (89.406bp,46.931bp) and (91.75bp,56.306bp) .. (98bp,56.306bp) .. controls (102bp,56.306bp) and (104.4bp,52.458bp) .. node[auto] {$a$} (q1);
+ \draw [->] (q0) ..controls (9.4062bp,46.931bp) and (11.75bp,56.306bp) .. (18bp,56.306bp) .. controls (22.004bp,56.306bp) and (24.405bp,52.458bp) .. node[auto] {$a$} (q0);
+%
+\end{tikzpicture}
+
+%%% end example1 %%%
+\end{center}
+
%
%