diff options
| -rw-r--r-- | exercices2.tex | 148 |
1 files changed, 148 insertions, 0 deletions
diff --git a/exercices2.tex b/exercices2.tex new file mode 100644 index 0000000..e100e11 --- /dev/null +++ b/exercices2.tex @@ -0,0 +1,148 @@ +%% 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 algébriques — Corrigé} +\else +\title{TD langages algébriques} +\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 = \{a,b\}$. Montrer que le langage $L := \{ww : +w\in\Sigma^*\}$ constitué des mots de la forme $ww$ (par exemple, +$\varepsilon$, $aa$, $abab$, $abaaba$ ou encore $aabbaabb$) n'est pas +algébrique. On pourra pour considérer son intersection avec le +langage $L_0$ dénoté par l'expression rationnelle $a{*}b{*}a{*}b{*}$ +et appliquer le lemme de pompage. + +\begin{corrige} +Supposons par l'absurde que $L$ soit algébrique : alors son +intersection avec le langage rationnel $L_0 = \{a^m b^n a^{m'} b^{n'} : +m,n,m',n' \in \mathbb{N}\}$ est encore algébrique. Or $L \cap L_0 = +\{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$. On va maintenant utiliser +le lemme de pompage pour arriver à une contradiction. + +Appliquons le lemme de pompage pour les langages algébriques au +langage $L \cap L_0 = \{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$ +considéré : appelons $k$ l'entier dont le lemme de pompage garantit +l'existence. Considérons le mot $t := a^k b^k a^k b^k$ : dans la +suite de cette démonstration, on appellera « bloc » de $t$ un des +quatre facteurs $a^k$, $b^k$, $a^k$ et $b^k$. D'après la propriété de +$k$ garantie par le lemme de pompage, il doit exister une +factorisation $t = uvwxy$ pour laquelle on a (i) $|vx|\geq 1$, +(ii) $|vwx|\leq k$ et (iii) $uv^iwx^iy \in L \cap L_0$ pour +tout $i\geq 0$. + +Chacun de $v$ et de $x$ doit être contenu dans un seul bloc, i.e., +doit être de la forme $a^\ell$ ou $b^\ell$, sinon sa répétition ($v^i$ +ou $x^i$ pour $i\geq 2$, qui appartient à $L_0$ d'après (iii)) ferait +apparaître plus d'alternations entre $a$ et $b$ que le langage $L_0$ +ne le permet. Par ailleurs, la propriété (ii) assure que le facteur +$vwx$ ne peut rencontrer qu'un ou deux blocs de $t$ (pas plus). +Autrement dit, $v$ et $x$ sont contenus dans deux blocs de $t$ qui +sont identiques ou bien consécutifs\footnote{La formulation est + choisie pour avoir un sens même si $v$ ou $x$ est le mot vide (ce + qui est possible \textit{a priori}).}. + +D'après la propriété (i), au moins l'un de $v$ et de $x$ n'est pas le +mot vide. Si ce facteur non trivial est dans le premier bloc $a^k$, +l'autre ne peut pas être dans l'autre bloc $a^k$ d'après ce qui vient +d'être dit : donc $uv^iwx^iy$ est de la forme $a^{k'} b^n a^k b^k$ +avec $k'>k$ si $i>1$, qui n'appartient pas à $L\cap L_0$, une +contradiction. De même, le facteur non trivial est dans le premier +bloc $b^k$, l'autre ne peut pas être dans l'autre bloc $b^k$ : donc +$uv^iwx^iy$ est de la forme $a^m b^{k'} a^{m'} b^k$ avec $k'>k$ si +$i>1$, qui n'appartient pas à $L\cap L_0$, de nouveau une +contradiction. Les deux autres cas sont analogues. +\end{corrige} + + +% +% +% +\end{document} |