From de5663ac0f366f6d751599983a70b743ca549017 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 29 Nov 2016 16:48:08 +0100 Subject: Write an exercise on rational languages. --- exercices1.tex | 217 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ figs/ex1p1.dot | 11 +++ 2 files changed, 228 insertions(+) create mode 100644 exercices1.tex create mode 100644 figs/ex1p1.dot 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"]; +} -- cgit v1.2.3