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
|
%% 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}
|
