summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-12 16:09:10 +0100
committerDavid A. Madore <david+git@madore.org>2017-01-12 16:09:10 +0100
commit015c498faaae339ed54c3bf698ab98ab9f83d768 (patch)
treee21fa169376ab19b79cfd75f78ea517913b2dc9d
parenta90393e3982a38acaa3798c80e811186c005bc58 (diff)
downloadinf105-015c498faaae339ed54c3bf698ab98ab9f83d768.tar.gz
inf105-015c498faaae339ed54c3bf698ab98ab9f83d768.tar.bz2
inf105-015c498faaae339ed54c3bf698ab98ab9f83d768.zip
An exercise applying the pumping lemma for algebraic languages.
-rw-r--r--exercices2.tex148
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}