%% 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}\smallskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
\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\par\smallbreak\else\egroup\par\fi}
\newenvironment{commentaire}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
{{\hbox{}\nobreak\hfill\maltese}%
\ifcorrige\par\smallbreak\else\egroup\par\fi}
%
%
% 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{23 janvier 2020}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Les exercices sont totalement indépendants.  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 appareils électroniques est interdit.

\medbreak

Durée : 1h30

Barème \emph{indicatif} : \textcolor{red}{(à remplir)}.

\ifcorrige
Ce corrigé comporte \textcolor{red}{(à remplir)} pages (page de garde incluse)
\else
Cet énoncé comporte \textcolor{red}{(à remplir)} pages (page de garde incluse)
\fi

\vfill

{\tiny\noindent
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pagebreak


%
%
%

\exercice

Soit $\mathscr{A}$ l'automate suivant sur l'alphabet $\Sigma :=
\{a,b,c\}$ :

\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$};
\draw [->] (S0) -- node[auto,near end] {$\varepsilon$} (S1);
\draw [->] (S0) -- node[auto,below] {$\varepsilon$} (S2);
\draw [->] (S1) to[out=225,in=135] node[auto,left] {$a$} (S2);
\draw [->] (S2) to[out=45,in=315] node[auto,right] {$b$} (S1);
\draw [->] (S2) to[loop below] node[auto] {$c$} (S2);
\draw [->] (S1) -- node[auto] {$\varepsilon$} (S3);
\draw [->] (S2) -- node[auto,below,near end] {$\varepsilon$} (S3);
\end{tikzpicture}
\end{center}

\vskip-\baselineskip\vskip-.5ex\noindent En lui appliquant la méthode
d'élimination des états, déterminer une expression rationnelle
dénotant le langage qu'il reconnaît.


%
%
%

\exercice

Dans cet exercice, on pose $\Sigma := \{a\}$ (alphabet à une seule lettre).

\medskip

\textbf{Première partie : étude d'un cas particulier.}

Dans cette partie, on considère l'expression rationnelle $r$
suivante : $(aaa|aaaaa){*}$ (sur l'alphabet $\Sigma$).  On appelle $L
:= L(r)$ le langage qu'elle dénote et $M := \Sigma^* \setminus L$ son
complémentaire.

(1) Traiter l'une \emph{ou} l'autre des questions suivantes :
(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ;
(ii) construire l'automate de Thompson de $r$, puis éliminer les
transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on
retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$
l'automate ainsi obtenu.

(Dans les deux cas, on obtient le même automate $\mathscr{A}_1$, ayant
$9$ états.  À défaut de donner l'automate de Glushkov ou de Thompson,
donner un NFA reconnaissant $L$ pourra apporter une partie des
points.)

(2) Déterminiser l'automate $\mathscr{A}_1$.  On appellera
$\mathscr{A}_2$ l'automate (déterministe complet) en question.

(On obtient un automate $\mathscr{A}_2$ ayant $14$ états.  On
n'hésitera pas à introduire des notations simplificatrices si on le
juge utile ; il pourra être judicieux de réfléchir au préalable à une
façon de nommer les états de $\mathscr{A}_1$ qui rend la construction
de $\mathscr{A}_2$ plus facile à mener sans se tromper.)

Pour simplifier les questions suivantes (ainsi que le travail du
correcteur), on renommera si nécessaire les états de $\mathscr{A}_2$
de façon que, autant que possible, l'état résultant de la lecture du
mot $a^k$ par l'automate soit numéroté $k$.

(3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
$\mathscr{A}_3$ l'automate canonique ainsi obtenu.

(On obtient un automate ayant $9$ états.)

(4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M
:= \Sigma^*\setminus L$ complémentaire de $L$.  Ce langage $M$ est
fini : énumérer exhaustivement les mots qu'il contient.

(5) En utilisant la question précédente, dire quels sont les entiers
naturels ne pouvant pas s'écrire sous la forme $3m+5m'$ avec
$m,m'\in\mathbb{N}$.

\medbreak

\textbf{Seconde partie : considérations générales.}

(6) Expliquer rapidement pourquoi un automate déterministe complet
$\mathscr{A}$ sur $\Sigma$ prend nécessairement la forme suivante : si
on note $j_2$ son nombre d'états, on peut numéroter ses états de
$0$ à $j_2-1$, avec $0$ l'état initial, et de façon qu'il y ait une
unique transition étiquetée $a$ de l'état $i$ vers l'état $i+1$ pour
chaque $0\leq i<j_2-1$, ainsi qu'une transition étiquetée $a$ de
l'état $j_2-1$ vers l'état $j_1$ pour un certain $0\leq j_1<j_2$.
Remarquer que l'automate $\mathscr{A}$ est alors complètement décrit
par les entiers $0\leq j_1<j_2$ et par le sous-ensemble $F$ de
$\{0,\ldots,j_2-1\}$ formé des états finaux.

(7) Une fois un automate déterministe complet sur $\Sigma$ présenté
comme décrit à la question (6), à quelle condition le langage qu'il
reconnaît est-il fini ?

(8) Déduire de l'ensemble de cet exercice que le problème suivant est
calculable algorithmiquement\footnote{Autrement dit, montrer qu'il
  existe un algorithme qui, prenant en entrée $\ell_1,\ldots,\ell_r
  \in \mathbb{N}$, répond au problème posé.} : donné des entiers
naturels $\ell_1,\ldots,\ell_r \in \mathbb{N}$, décider s'il y a un
nombre fini d'entiers naturels qui ne peuvent pas s'écrire sous la
forme $\ell_1 m_1 + \cdots + \ell_r m_r$ avec $m_1,\ldots,m_r \in
\mathbb{N}$, et, le cas échéant, les énumérer.


%
%
%

\exercice

On considère la grammaire hors-contexte $G$ d'axiome $S$ et de
nonterminaux $N = \{S, T, U\}$ sur l'alphabet $\Sigma = \{a,b,c\}$
donnée par
\[
\begin{aligned}
S &\rightarrow T \;|\; TaS\\
T &\rightarrow U \;|\; UbT\\
U &\rightarrow c\\
\end{aligned}
\]
(La grammaire en question est inambiguë : on ne demande pas de le
démontrer.)

(1) Donner les arbres d'analyse (= de dérivation) des mots suivants :
$cacbcac$ et $cbcacbc$.

(2) Expliquer pourquoi le langage $L := L(G)$ engendré par $G$ est, en
fait, rationnel et donner une expression rationnelle qui le dénote.
(On pourra commencer par décrire le langage $L' := L(G,T) := \{w \in
\Sigma^* : T \mathrel{\Rightarrow^*_G} w\}$ des mots qui dérivent
de $T$ dans $G$.)


%
%
%
\end{document}