summaryrefslogtreecommitdiffstats
path: root/controle-20190328.tex
blob: e3e13910f75916ebb6488a0c0d51220b97d76075 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
%% 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 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.}

\textcolor{red}{À remplir}

\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}{xxx}.

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

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 passera impérativement par 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 « moir »
$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$ 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 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).

%
%
%
\end{document}