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