diff options
| -rw-r--r-- | figs/example1.dot | 11 | ||||
| -rw-r--r-- | notes-inf105.tex | 99 |
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} + % % |