Write an exercise on rational languages.

2 files changed, 228 insertions, 0 deletions

diff --git a/exercices1.tex b/exercices1.tex
new file mode 100644
index 0000000..26533e8
--- /dev/null
+++ b/exercices1.tex
@@ -0,0 +1,217 @@
+%% 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}
+
+
+%
+%
+%
+\end{document}
diff --git a/figs/ex1p1.dot b/figs/ex1p1.dot
new file mode 100644
index 0000000..6625c8a
--- /dev/null
+++ b/figs/ex1p1.dot
@@ -0,0 +1,11 @@
+digraph ex1p1 {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	qX [style="state,initial",label="X"];
+	qY [style="state,final",label="Y"];
+	qZ [style="state,final",label="Z"];
+	edge [texmode="math",lblstyle="auto"];
+	qX -> qY [label="0"];
+	qX -> qZ [label="1"];
+	qZ -> qZ [label="0,1",topath="loop below"];
+}