%% 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.}}
\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 rattrapage — Corrigé\\{\normalsize Théorie des langages}}
\else
\title{INF105\\Contrôle de rattrapage\\{\normalsize Théorie des langages}}
\fi
\author{}
\date{22 mars 2018}
\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 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

\pagebreak


%
%
%

\exercice

Dans cet exercice, on pose $\Sigma = \{a,b,c\}$.  On appelle $L$ le
langage des mots sur $\Sigma$ qui ont $abc$ comme sous-mot,
c'est-à-dire, qui contiennent un $a$, un $b$ et un $c$ dans cet ordre
mais non nécessairement consécutivement (à titre d'exemple, $abac \in
L$).

(1) Proposer un automate non-déterministe (NFA), sans transition
spontanée, $\mathscr{A}_1$ qui reconnaît le langage $L$.  On
justifiera rapidement pourquoi l'automate proposé convient.

(2) Déterminiser (si nécessaire) l'automate $\mathscr{A}_1$ trouvé
en (1) ; on appellera $\mathscr{A}_2$ l'automate résultant.

(3) Minimiser (si nécessaire) l'automate $\mathscr{A}_2$ obtenu
en (2) ; on appellera $\mathscr{A}_3$ l'automate minimal (=canonique)
résultant.

(4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M
:= \Sigma^*\setminus L$ complémentaire de $L$.

(5) En appliquant à $\mathscr{A}_4$ la méthode d'élimination des
états, déterminer une expression rationnelle dénotant le langage $M$.


%
%
%

\exercice

Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On appelle $L = L(G)$
le langage défini par la hors-contexte $G$ d'axiome $S$ et de
nonterminaux $N = \{S\}$ sur l'alphabet $\Sigma$ donnée par
\[
\begin{aligned}
S &\rightarrow aSbS \;|\; aS \;|\; \varepsilon\\
\end{aligned}
\]

(1) Donner deux arbres d'analyse (pour $G$) différents du mot $aab$.
Que peut-on dire de la grammaire $G$ ?

L'objet des questions suivantes (qui ne dépendent pas de la
précédente) est de montrer que $L$ n'est pas rationnel.

Soit $M$ le langage $\{a^i b^j : i,j\in\mathbb{N}\}$ constitué des
mots de la forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels
quelconques.

(2) Donner une expression rationnelle qui dénote $M$.

Soit $P$ le langage $\{a^i b^j : i\geq j\}$ constitué des mots de la
forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels vérifiant $i\geq
j$ (autrement dit, les mots de $M$ qui ont au moins autant de $a$ que
de $b$).

(3) Montrer que $P \subseteq L$.

(4) Montrer que $L\cap M \subseteq P$.

(5) Montrer que $P$ n'est pas rationnel.

(6) Déduire des questions (2) à (5) que $L$ n'est pas rationnel.


%
%
%
\end{document}