%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\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}
\usepackage{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\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{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\ifcorrige
\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}}
\else
\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
\fi
\author{}
\date{7 février 2017}
\maketitle

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

\vskip1truein\relax

\noindent\textbf{Consignes.}

Les exercices sont indépendants sauf dans la mesure où le contraire
est précisé.  Ils pourront être traités dans un ordre quelconque, mais
on demande de faire apparaître de façon très visible dans les copies
où commence chaque exercice.

\medbreak

L'usage de tous les documents (notes de cours manuscrites ou
imprimées, feuilles d'exercices, livres) est autorisé.

L'usage des calculatrices électroniques est interdit.

\medbreak

Durée : 1h30

\pagebreak


%
%
%

\exercice

On considère l'automate fini sur l'alphabet $\Sigma = \{a,b\}$
représenté par la figure suivante :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$};
\node (Y) at (80bp,0bp) [draw,circle,state,final] {$Y$};
\node (A1) at (-40bp,50bp) [draw,circle,state] {$A$};
\node (A2) at (40bp,50bp) [draw,circle,state] {$A'$};
\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B$};
\node (B2) at (40bp,-50bp) [draw,circle,state] {$B'$};
\draw[->] (X) -- node[auto]{$\varepsilon$} (A1);
\draw[->] (X) -- node[auto,below left]{$\varepsilon$} (B1);
\draw[->] (A1) -- node[auto]{$a$} (A2);
\draw[->] (B1) -- node[auto]{$b$} (B2);
\draw[->] (A1) to[loop above] node[auto]{$b$} (A1);
\draw[->] (A2) to[loop above] node[auto]{$b$} (A2);
\draw[->] (B1) to[loop below] node[auto]{$a$} (B1);
\draw[->] (B2) to[loop below] node[auto]{$a$} (B2);
\draw[->] (A2) -- node[auto]{$\varepsilon$} (Y);
\draw[->] (B2) -- node[auto,below right]{$\varepsilon$} (Y);
\end{tikzpicture}
\end{center}

(0) De quelle sorte d'automate s'agit-il ?  (Autrement dit : est-il
déterministe ou non ? avec transitions spontanées ou non ?)

(1) Décrire brièvement, en français, le langage reconnu (=accepté) par
l'automate en question, puis donner une expression rationnelle qui le
dénote.

(2) Éliminer les transitions spontanées de l'automate, s'il y en a.
(On supprimera les états devenus inutiles.)

(3) Déterminiser l'automate ainsi obtenu, si nécessaire.  (On demande
un automate déterministe complet.)  Pour simplifier le travail du
correcteur, on demande de faire en sorte que les transitions
étiquetées par $a$ soient, dans la mesure du possible, horizontales de
la gauche vers la droite, et celles étiquetées par $b$, verticales du
haut vers le bas.

\begin{corrige}
(0) Il s'agit d'un automate non-déterministe à transitions spontanées,
  ou ε-NFA (il n'y a pas de notion d'automate déterministe à
  transitions spontanées).

(1) Le chemin par les états $X,A,A',Y$ accepte les mots comportant un
  et un seul $a$, c'est-à-dire le langage dénoté par $b{*}ab{*}$.  Le
  chemin par les états $X,B,B',Y$ accepte les mots comportant un et un
  seul $b$, c'est-à-dire le langage dénoté par $a{*}ba{*}$.
  L'automate dans son ensemble accepte les mots comportant soit un
  unique $a$, soit un unique $b$ (i.e. $\{w\in\Sigma^* : |w|_a = 1
  \penalty0\ \textrm{ou}\penalty0\ |w|_b = 1\}$ si $|w|_x$ désigne le
  nombre total d'occurrences de la lettre $x$ dans le mot $w$).  C'est
  le langage dénoté par l'expression rationnelle $b{*}ab{*} |
  a{*}ba{*}$.

(2) La ε-fermeture de l'état $X$ est $\{X,A,B\}$ ; la ε-fermeture de
  l'état $A'$ est $\{A',Y\}$ et celle de l'état $B'$ est $\{B',Y\}$ ;
  les autres états sont leur propre ε-fermeture (i.e., celle-ci est un
  singleton).  L'élimination des transitions spontanées conduit donc à
  l'automate suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$};
\node (A1) at (-40bp,50bp) [draw,circle,state] {$A$};
\node (A2) at (40bp,50bp) [draw,circle,state,final] {$A'$};
\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B$};
\node (B2) at (40bp,-50bp) [draw,circle,state,final] {$B'$};
\draw[->] (X) -- node[auto]{$b$} (A1);
\draw[->] (X) -- node[auto,below left]{$a$} (B1);
\draw[->] (X) -- node[auto,below right]{$a$} (A2);
\draw[->] (X) -- node[auto,above right]{$b$} (B2);
\draw[->] (A1) -- node[auto]{$a$} (A2);
\draw[->] (B1) -- node[auto]{$b$} (B2);
\draw[->] (A1) to[loop above] node[auto]{$b$} (A1);
\draw[->] (A2) to[loop above] node[auto]{$b$} (A2);
\draw[->] (B1) to[loop below] node[auto]{$a$} (B1);
\draw[->] (B2) to[loop below] node[auto]{$a$} (B2);
\end{tikzpicture}
\end{center}
(On a supprimé l'état $Y$ qui est devenu inutile car aucune transition
non-spontanée n'y conduit.)

(3) L'algorithme de déterminisation conduit à l'automate suivant où,
pour plus de lisibilité, les états finaux ont été marqués en les
entourant deux fois plutôt que par une flèche sortante :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$\{X\}$};
\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$\{A',B\}$};
\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$\{B\}$};
\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A,B'\}$};
\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A',B'\}$};
\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{B'\}$};
\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$\{A\}$};
\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$\{A'\}$};
\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$\varnothing$};
\draw[->] (s00) -- node[auto]{$a$} (s01);
\draw[->] (s01) -- node[auto]{$a$} (s02);
\draw[->] (s10) -- node[auto]{$a$} (s11);
\draw[->] (s11) -- node[auto]{$a$} (s12);
\draw[->] (s20) -- node[auto]{$a$} (s21);
\draw[->] (s21) -- node[auto]{$a$} (s22);
\draw[->] (s02) to[loop right] node[auto]{$a$} (s02);
\draw[->] (s12) to[loop right] node[auto]{$a$} (s12);
\draw[->] (s22) to[loop right] node[auto]{$a$} (s22);
\draw[->] (s00) -- node[auto]{$b$} (s10);
\draw[->] (s10) -- node[auto]{$b$} (s20);
\draw[->] (s01) -- node[auto]{$b$} (s11);
\draw[->] (s11) -- node[auto]{$b$} (s21);
\draw[->] (s02) -- node[auto]{$b$} (s12);
\draw[->] (s12) -- node[auto]{$b$} (s22);
\draw[->] (s20) to[loop below] node[auto]{$b$} (s20);
\draw[->] (s21) to[loop below] node[auto]{$b$} (s21);
\draw[->] (s22) to[loop below] node[auto]{$b$} (s22);
\end{tikzpicture}
\end{center}
\end{corrige}



%
%
%
\end{document}