%% 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
\corrigefalse
\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{28 mars 2019}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Les exercices sont indépendants.  Il est recommandé de les traiter
dans l'ordre du sujet, mais ce n'est pas nécessaire ; cependant, 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} : 11+4+5.

\ifcorrige
Ce corrigé comporte \textcolor{red}{xxx} pages (page de garde incluse)
\else
Cet énoncé comporte 3 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\label{exercise-on-finite-automata}

Dans cet exercice, on pose $\Sigma = \{a,b\}$.

(1) Soit $L_1$ le langage formé des mots de $\Sigma^*$ ayant $a$ comme
première lettre (c'est-à-dire, comme préfixe).\quad(a) Donner une
expression rationnelle $r_1$ dénotant le langage $L_1$.\quad(b) Donner
l'automate fini déterministe complet minimal $\mathscr{A}_1$
reconnaissant $L_1$ (on pourra préalablement passer par d'autres
sortes d'automates comme étapes intermédiaires ; pour obtenir la
totalité des points, on utilisera impérativement des constructions
vues en cours, qu'on précisera).

\emph{Information :} L'automate $\mathscr{A}_1$ correct a trois états.
Il est fortement conseillé de vérifier soigneusement qu'on a bien
obtenu un automate déterministe complet ayant le bon nombre états et
qu'il se comporte comme attendu sur quelques mots courts (par exemple
$\varepsilon$, $a$, $b$, $aa$, $ab$, $ba$ et $bb$).

\medskip

(2) Soit $L_2$ le langage formé des mots de $\Sigma^*$ ayant $a$ comme
dernière lettre (c'est-à-dire, comme suffixe).\quad(a) Donner une
expression rationnelle $r_2$ dénotant le langage $L_2$.\quad(b) Donner
l'automate fini déterministe complet minimal $\mathscr{A}_2$
reconnaissant $L_2$ (mêmes remarques que ci-dessus).

\emph{Information :} L'automate $\mathscr{A}_2$ correct a deux états.
Même conseil que ci-dessus.

\medskip

(3) Soit $L_3 = L_2^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L_2\}$ le
langage miroir de $L_2$, c'est-à-dire le langage formé des mots
miroirs des mots de $L_2$ (on rappelle que le mot « miroir »
$w^{\mathsf{R}}$ d'un mot $w$ s'obtient en inversant l'ordre de ses
lettres).\quad(a) Déduire de $\mathscr{A}_2$ un automate fini
$\mathscr{A}_3$ reconnaissant $L_3$.\quad(b) Quel est le rapport entre
les langages $L_1$ et $L_3$ ?\quad(c) Faire un commentaire quant au
rapport entre $\mathscr{A}_1$ et $\mathscr{A}_3$ ; notamment, on
expliquera en quoi l'existence de $\mathscr{A}_3$ ne contredit pas la
minimalité de $\mathscr{A}_1$.

\medskip

(4) Soit $L_4 = L_1\cap L_2$.\quad(a) Déduire des automates
$\mathscr{A}_1$ et $\mathscr{A}_2$ un automate fini
$\mathscr{A}_{4\mathrm{a}}$ ayant six états
reconnaissant $L_4$.\quad(b) Donner l'automate fini déterministe
complet minimal $\mathscr{A}_{4\mathrm{b}}$ reconnaissant $L_4$.

\emph{Information :} L'automate $\mathscr{A}_{4\mathrm{b}}$ correct a
quatre états.  Même conseil que pour la question (1).

\medskip

(5) En appliquant l'algorithme d'élimination des états, déduire
de $\mathscr{A}_{4\mathrm{b}}$ une expression rationnelle $r_5$
dénotant le langage $L_4$.

\medskip

(6) Sans raisonner sur les automates, proposer directement une
expression rationnelle $r_6$ différente de celle trouvée en $r_5$ et
qui dénote aussi le langage $L_4$ (dont on donnera au préalable une
description en français).


%
%
%

\exercice\label{exercise-two}

Dans cet exercice, on pose $\Sigma = \{a,b\}$.

Soit $L$ le langage formé des mots de $\Sigma^*$ ayant à la fois
$a$ comme première lettre et aussi comme dernière lettre
(c'est-à-dire, les mots ayant $a$ comme préfixe et aussi $a$ comme
suffixe).

\smallskip

(1) (a) Expliciter une grammaire hors contexte $G$
engrendrant $L$.\quad(b) Cette grammaire $G$ est-elle déterministe ?
(On justifiera la réponse.)

\medskip

(2) La langage $L$ est-il décidable ?  Est-il semi-décidable ?  On
justifiera soigneusement la réponse.


%
%
%

\exercice\label{exercise-three}

Dans cet exercice, on pose $\Sigma = \{a\}$.

Soit $L = \{a, aa, aaaa, aaaaaaaa,\ldots\} = \{a^{2^k} :
k\in\mathbb{N}\}$ le langage formé des mots de $\Sigma^*$ dont la
longueur est une puissance de $2$.

\smallskip

(1) Le langage $L$ est-il rationnel ?  Si oui, on explicitera une
expression rationnelle le dénotant ; si non, on démontrera ce fait.

\medskip

(2) Le langage $L$ est-il algébrique (autrement dit, existe-t-il une
grammaire hors contexte $G$ engendrant $L$) ?  Si oui, on explicitera
une grammaire hors contexte l'engendrant ; si non, on démontrera ce
fait.

\medskip

(3) La langage $L$ est-il décidable ?  Est-il semi-décidable ?  Comme
pour les questions précédentes, on justifiera soigneusement la
réponse.

\medskip

\emph{Remarque :} Il est loisible de répondre aux questions de cet
exercice dans un ordre différent par exemple pour éviter de répéter
inutilement des raisonnements.

%
%
%
\end{document}