summaryrefslogtreecommitdiffstats
path: root/controle-20200123.tex
blob: f87eb0e08c3419f953afe226398a55029f7c1da2 (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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
%% 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}