path: root/exercices1.tex

%% 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[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\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\relax\else\egroup\fi\par}
%
%
% 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{TD langages rationnels — Corrigé}
\else
\title{TD langages rationnels}
\fi
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

{\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


%
%
%

\exercice

Soit $\Sigma = \{0,1\}$.  On appelle \emph{mot binaire} un mot sur
l'alphabet $\Sigma$, et mot binaire \emph{normalisé} un mot binaire
qui \emph{soit} commence par $1$, \emph{soit} est exactement égal
à $0$.

(1) Montrer que le langage $L_n = \{0, 1, 10, 11, 100, 101,\ldots\}$
des mots binaires normalisés est rationnel en exhibant directement une
expression rationnelle qui le dénote, et montrer qu'il est
reconnaissable en exhibant directement un automate fini qui le
reconnaît.

(2) On définit la \emph{valeur numérique} d'un mot sur $\Sigma$
(=: mot binaire) $x_{n-1}\cdots x_0$ comme $\sum_{i=0}^{n-1} x_i 2^i$
(où $x_i$ vaut $0$ ou $1$ et est numéroté de $0$ pour le chiffre le
plus à droite à $n-1$ pour le plus à gauche) ; la valeur numérique du
mot vide $\varepsilon$ est $0$.

Parmi les langages suivants, certains sont rationnels, d'autres ne le
sont pas.  Dire lesquels sont rationnels et justifier brièvement
pourquoi (on ne demande pas de justifier pourquoi ceux qui ne sont pas
rationnels ne le sont pas) :

(a) le langage $L_a$ des mots binaires dont la valeur numérique est
paire,

(b) le langage $L_b$ des mots binaires \emph{normalisés} dont la
valeur numérique est paire,

(c) le langage $L_c$ des mots binaires dont la valeur numérique est
multiple de $3$ (indication : selon que $n$ est congru à $0$, $1$ ou
$2$ modulo $3$, et selon que $x$ vaut $0$ ou $1$, à quoi est congru
$2n+x$ modulo $3$ ?),

(d) le langage $L_d$ des mots binaires dont la valeur numérique est un
nombre premier,

(e) le langage $L_e$ des mots binaires dont la valeur numérique est
une puissance de $2$,

\begin{corrige}
(1) On peut écrire $L_n = L_r$, langage dénoté par l'expression
  rationnelle $r := 0|1(0|1){*}$.  Ce langage est reconnu, par
  exemple, par le DFAI suivant :
\begin{center}
%%% begin ex1p1 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (qY) at (97bp,105bp) [draw,circle,state,final] {$Y$};
  \node (qX) at (18bp,74bp) [draw,circle,state,initial] {$X$};
  \node (qZ) at (97bp,18bp) [draw,circle,state,final] {$Z$};
  \draw [->] (qX) ..controls (45.279bp,84.58bp) and (58.943bp,90.081bp)  .. node[auto] {$0$} (qY);
  \draw [->] (qX) ..controls (44.52bp,55.44bp) and (60.758bp,43.63bp)  .. node[auto] {$1$} (qZ);
  \draw [->] (qZ) to[loop below] node[auto] {$0,1$} (qZ);
%
\end{tikzpicture}

%%% end ex1p1 %%%
\end{center}

(2) (a) Le langage $L_a$ est rationnel car il s'agit du langage des
mots binaires qui soit sont le mot vide soit finissent par $0$ : il
est dénoté par l'expression rationnelle
$\underline{\varepsilon}|(0|1){*}0$.\spaceout (b) On a $L_b = L_a \cap
L_n$ et on a vu que $L_a$ et $L_n$ sont rationnels, donc $L_b$ l'est
aussi.

(c) Ajouter un $0$ ou un $1$ à la fin d'un mot binaire de valeur
numérique $n$ le transforme en un mot de valeur numérique $2n+x$
où $x$ est le chiffre affixé.  Considérons les six combinaisons entre
les trois cas possibles de la valeur numérique $n$ modulo $3$ et les
deux cas possibles de la valeur de $x$ :
\begin{center}
\begin{tabular}{c|c|c}
$n\equiv?\pmod{3}$&$x=?$&$2n+x\equiv?\pmod{3}$\\\hline
$0$&$0$&$0$\\
$0$&$1$&$1$\\
$1$&$0$&$2$\\
$1$&$1$&$0$\\
$2$&$0$&$1$\\
$2$&$1$&$2$\\
\end{tabular}
\end{center}
Ceci définit un DFA dont les trois états correspondent aux trois
valeurs possibles de $n$ modulo $3$, la transition $n\to n'$ étiquetée
par $x$ correspond au passage de $n$ à $2n+x$ modulo $3$,
c'est-à-dire :
\begin{center}
%%% begin example6 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$0$};
  \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$};
  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$1$} (q0);
  \draw [->] (q2) to[loop above] node[auto] {$1$} (q2);
  \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp)  .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp)  .. node[auto] {$0$} (q1);
  \draw [->] (q0) to[loop above] node[auto] {$0$} (q0);
  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$1$} (q1);
  \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$0$} (q2);
%
\end{tikzpicture}

%%% end example6 %%%
\end{center}
(On a marqué l'état $0$ comme initial car le mot vide a une valeur
numérique congrue à $0$ modulo $3$, et seul $0$ comme final car on
veut reconnaître les multiples de $3$.)

(d) Le langage $L_d$ n'est pas rationnel (on pourrait le démontrer à
l'aide du lemme de pompage, mais ce n'est pas très facile).

(e) Le langage $L_e$ est rationnel car il s'agit du langage des dénoté
par l'expression rationnelle $10{*}$.
\end{corrige}


%
%
%

\exercice

Soit $\Sigma = \{a\}$.  Montrer que le langage $L = \{a^2, a^3, a^5,
a^7, a^{11}, a^{13}\ldots\}$ constitué des mots ayant un nombre
\emph{premier} de $a$, n'est pas rationnel.

\begin{corrige}
Supposons par l'absurde que $L$ soit rationnel.  D'après le lemme de
pompage, il existe un certain $k$ tel que tout mot de $L$ de longueur
$\geq k$ se factorise sous la forme $uvw$ avec (i) $|v|\geq 1$,
(ii) $|uv|\leq k$ et (iii) $uv^iw \in L$ pour tout $i\geq 0$.  Soit
$p$ un nombre premier supérieur ou égal à $k$ : le mot $a^p \in L$
admet une factorisation comme on vient de dire.  Posons $|u| =: m$ et
$|v| =: n$, si bien que $|w| = p-m-n$.  On a alors $n\geq 1$
d'après (i), et $|uv^iw| = m + in + (p-m-n) = p+(i-1)n$ est premier
pour tout $i\geq 0$ d'après (iii).  En particulier pour $i=p+1$ on
voit que $p + pn = p(n+1)$ est premier, ce qui contredit le fait qu'il
s'agit d'un multiple non-trivial ($n+1\geq 2$) de $p$.
\end{corrige}


%
%
%
\end{document}