1285 lines
65 KiB
Plaintext
1285 lines
65 KiB
Plaintext
|
\documentclass[11pt,a4paper,titlepage,twoside]{article}
|
||
|
|
|
||
|
|
\input{Preambule.tex} % Toutes les instructions du préambule sont dans un fichier séparé qui est utilisé pour tous les cours.
|
||
|
|
% Il faut le mettre à l'extérieur du dossier dans lequel se trouve le cours --> ../Preambule.tex
|
||
|
|
|
||
|
|
\usepackage{geometry} % La seule présence de ce paquet élargit les marges correctement
|
||
|
|
|
||
|
|
\lstloadlanguages{python,TeX,XML} % chargement des languages nécessaires (ici un seul)
|
||
|
|
%\lstset{language=TeX} % language choisi par défaut
|
||
|
|
|
||
|
|
\setlength{\headheight}{22.6pt} % pour élargir un peu l'entête
|
||
|
|
%\setcounter{tocdepth}{5} % pour définir la profondeur de la table des matières
|
||
|
|
%\renewcommand{\thefootnote}{\alph{footnote}} % pour mettre les notes de bas de page en alphabétique
|
||
|
|
|
||
|
|
%\usepackage{etex}
|
||
|
|
%\usepackage[all,2cell]{xy}
|
||
|
|
%\UseAllTwocells
|
||
|
|
%\usepackage{xymtex} % pour la représentation de molécules chimiques
|
||
|
|
%\let\urlorig\url % pour mettre des deux points dans les url, passage en langue anglaise
|
||
|
|
%\renewcommand{\url}[1]{%
|
||
|
|
% \begin{otherlanguage}{english}\urlorig{#1}\end{otherlanguage}%
|
||
|
|
%}
|
||
|
|
%\usepackage[colorlinks=true,linkcolor=black,urlcolor=blue,pagebackref,frenchlinks]{hyperref}
|
||
|
|
\usepackage{eurosym}
|
||
|
|
\usepackage{textcomp}
|
||
|
|
\usepackage{auto-pst-pdf}
|
||
|
|
\usepackage{vaucanson-g}
|
||
|
|
%\usepackage{algorithm,algorithmique}
|
||
|
|
\usepackage[french,boxruled]{algorithm2e}
|
||
|
|
|
||
|
|
\setlength{\headheight}{13.6pt} % spécifie la hauteur de l'entête pour qu'elle ne couvre pas le titre
|
||
|
|
|
||
|
|
\setcounter{topnumber}{3} % nombre maximal de flottant en haut d'une page (par défaut 2)
|
||
|
|
\setcounter{bottomnumber}{2} % nombre maximal de flottant en bas d'une page (par défaut 1)
|
||
|
|
%\setcounter{totalnumber}{3} % nombre maximal de flottant sur une page (par défaut 3)
|
||
|
|
\renewcommand{\topfraction}{0.9} % proportion maximale de la page qui peut recevoir des flottants en haut de la page (par défaut 0,7)
|
||
|
|
\renewcommand{\textfraction}{0.1} % proportion minimale d'une page qui reçoit du texte (sans les pages de flottants)
|
||
|
|
\renewcommand{\floatpagefraction}{0.8} % proportion minimale de flottants sur une page pour qu'elle devienne une page uniquement de flottants
|
||
|
|
\renewcommand{\bottomfraction}{0.5} % proportion maximale de la page qui peut recevoir des flottants en bas de la page (par défaut 0,3)
|
||
|
|
|
||
|
|
\usepackage{answers} % pour utiliser le module answers
|
||
|
|
\Newassociation{sol}{Solution}{ans} % définition de l'étiquette Solution du module answers
|
||
|
|
\newtheorem{exc}{Exercice} % définition de l'étiquette Exercice du module answers
|
||
|
|
\newenvironment{ex}{\begin{exc}\normalfont}{\end{exc}} % cela (\normalfont) annule l'italique des énoncés des exercices
|
||
|
|
|
||
|
|
\graphicspath{{./Images/}{./Introduction/Images/}}
|
||
|
|
|
||
|
|
%\fancyhead[RE,LO]{Lycée Blaise Cendrars\\La Chaux-de-Fonds}
|
||
|
|
\fancyhead[LE,RO]{\thepage}
|
||
|
|
\lfoot{} \cfoot{} \rfoot{}
|
||
|
|
\pagestyle{fancy}
|
||
|
|
|
||
|
|
%\usepackage[firstpage]{draftwatermark}
|
||
|
|
%\SetWatermarkLightness{0.8}
|
||
|
|
%\SetWatermarkAngle{60}
|
||
|
|
%\SetWatermarkScale{0.8}
|
||
|
|
%\SetWatermarkFontSize{5cm}
|
||
|
|
%\SetWatermarkText{DOCUMENT À LAISSER AU LYCÉE}
|
||
|
|
|
||
|
|
\begin{document}
|
||
|
|
|
||
|
|
%\frontmatter
|
||
|
|
\newcommand\HRule{\noindent\rule{\linewidth}{1.5pt}}
|
||
|
|
\begin{titlepage}
|
||
|
|
\vspace*{\stretch{1}}
|
||
|
|
\HRule
|
||
|
|
\begin{flushright}
|
||
|
|
\LARGE Option complémentaire \\
|
||
|
|
\LARGE Informatique \\
|
||
|
|
\textsc{Langages formels et L-system}
|
||
|
|
\end{flushright}
|
||
|
|
\HRule\\
|
||
|
|
% \textsc{Document à laisser au lycée}
|
||
|
|
\vspace*{\stretch{2}}
|
||
|
|
\begin{center}
|
||
|
|
\today
|
||
|
|
\end{center}
|
||
|
|
\end{titlepage}
|
||
|
|
|
||
|
|
\section*{Copyright}
|
||
|
|
\addcontentsline{toc}{section}{Copyright}
|
||
|
|
Copyright (c) 2011 Guyot Vincent
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Permission vous est donnée de copier, distribuer et/ou modifier ce document selon les termes de la Licence GNU Free Documentation License, Version 1.1 ou ultérieure publiée par la Free Software Foundation.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
\begin{tabbing}\small
|
||
|
|
\hspace*{1cm}\=\hspace*{1cm}\=\kill
|
||
|
|
\>Avec les sections inaltérables suivantes :\\
|
||
|
|
\>\>\textit{Pas de section inaltérable}\\
|
||
|
|
\>avec le texte de première page de couverture suivant :\\
|
||
|
|
\>\>\textit{Option complémentaire \textsc{Informatique}}\\
|
||
|
|
\>avec le texte de dernière page de couverture suivant :\\
|
||
|
|
\>\>\textit{Pas de texte de texte de dernière page de couverture}\\
|
||
|
|
\end{tabbing}
|
||
|
|
|
||
|
|
Une copie transparente de ce document se trouve à l'adresse suivante :
|
||
|
|
www.cvgg.org
|
||
|
|
\begin{itemize}
|
||
|
|
\item Lsystem.tex : copie transparente,
|
||
|
|
\item Lsystem.dvi : copie opaque au format dvi.
|
||
|
|
\end{itemize}
|
||
|
|
|
||
|
|
\bigskip
|
||
|
|
Normalement une copie de la licence GFDL doit se trouver avec le présent document. Comme il est relativement court et comme on trouve facilement le texte de la GFDL sur internet, elle n'est pas reproduite ici pour ne pas utiliser inutilement du papier.
|
||
|
|
\thispagestyle{empty}
|
||
|
|
|
||
|
|
\newpage
|
||
|
|
|
||
|
|
\section*{Avertissement}
|
||
|
|
\addcontentsline{toc}{section}{Avertissement}
|
||
|
|
|
||
|
|
\thispagestyle{empty}
|
||
|
|
|
||
|
|
\tableofcontents{}
|
||
|
|
\addcontentsline{toc}{section}{Table des matières}
|
||
|
|
\thispagestyle{empty}
|
||
|
|
|
||
|
|
\newpage
|
||
|
|
|
||
|
|
%\mainmatter
|
||
|
|
|
||
|
|
\Opensolutionfile{ans}[Solutions] % ouvre le fichier Solutions.tex qui va contenir les solutions
|
||
|
|
|
||
|
|
\section{Introduction}
|
||
|
|
Ce cours s'adresse à des élèves dont les connaissances en informatiques se limitent à l'utilisation de logiciels et à des connaissances de base (boucles et fonctions) en programmation.
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Il ne s'adresse pas spécifiquement à des élèves non mathématiciens, car ceux-ci peuvent aussi y trouver de l'intérêt, mais surtout à des personnes qui ne se destinent ni à l'informatique, ni au mathématiques. C'est pourquoi, l'accent à été mis sur la plus grande clarté possible dans l'exposé des notions qui relèvent des mathématiques et sur les exemples. Il constitue à mon avis une approche adaptée pour des personnes intéressées par la biologie et par les langues.
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Les objectifs sont multiples.
|
||
|
|
\begin{description}
|
||
|
|
\item[Le premier] d'entre eux est de montrer aux élèves que l'analyse formelle est un préalable nécessaire à la compréhension des langages, en particulier informatiques.
|
||
|
|
\item[Le deuxième] est de présenter un exemple de la diversité des modes de représentation de ces langages.
|
||
|
|
\item[Le troisième] est d'illustrer le lien qui existe entre les langages et certains processus naturels, liens qui montre l'importance d'étude des formalismes présentés.
|
||
|
|
\item[Le dernier] objectif est finalement de permettre à l'élève d'utiliser des connaissances très sommaires de programmation pour analyser les processus mécaniquement dans des proportion inaccessibles à l'homme.
|
||
|
|
\end{description}
|
||
|
|
|
||
|
|
\section{Langage formel}
|
||
|
|
Rendre compte de la notion de langage formel le plus simplement possible n'est pas chose facile. Il se trouve que c'est la rigueur du langage mathématique qui permet d'en exprimer au mieux l'idée. Nous allons donc l'utiliser le plus simplement possible étant donné les difficultés qu'il peut représenter. Il sera néanmoins bien souvent plus une aide qu'un obstacle.
|
||
|
|
|
||
|
|
Tout langage est au départ constitué d'un alphabet. Il faut considérer le terme d'alphabet au sens large du terme comme un simple ensemble de signes ou lettres, même non alphabétiques au sens commun du terme. Ainsi, les ensembles suivants notés \(\Sigma_i\) constituent des exemples d'alphabet :
|
||
|
|
\begin{align*}
|
||
|
|
\Sigma_1 &= \{\text{\officialeuro, \maltese, \textleaf, \checkmark, 1, 4, \textvisiblespace}\}\\
|
||
|
|
\Sigma_2 &= \{\text{\textlnot, \textdollaroldstyle, \textcircled{a}, \pounds}\}\\
|
||
|
|
\Sigma_3 &= \{\text{a, b, \textvisiblespace, }\epsilon\}
|
||
|
|
\end{align*}
|
||
|
|
A partir de l'alphabet, on peut alors définir ce qu'est un mot. Il s'agit simplement d'une suite finie de lettres prises dans l'alphabet. Ainsi, on peut former les mots suivants sur l'alphabet \(\Sigma_1\) : \hspace{1cm}\officialeuro\officialeuro\maltese\officialeuro\officialeuro\checkmark\hspace{1cm} ou \hspace{1cm}\checkmark14\maltese\maltese\hspace{1cm} Pour l'alphabet \(\Sigma_3\), on pourrait avoir : \hspace{1cm}aababbab\hspace{1cm} ou \hspace{1cm}aabbbba \hspace{1cm}mais pas \hspace{1cm}aab\textlnot
|
||
|
|
|
||
|
|
Si m est un mot sur un alphabet \(\Sigma\), on écrira :
|
||
|
|
\[\text{m}\in\Sigma^*\]
|
||
|
|
pour dire que le mot m appartient à l'ensemble \(\Sigma^*\) des mot possibles formé sur l'alphabet \(\Sigma\). Finalement, on définit \(\epsilon\) comme un mot vide. La raison pour laquelle on fait cela sera vue plus tard.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Maintenant qu'on a des mots, le problème est de pouvoir les utiliser. Si on considère les mots suivants de \(\Sigma_3\) :
|
||
|
|
\[\text{abaab\textvisiblespace\hspace{1cm}}\text{aba\textvisiblespace\hspace{1cm}}\text{aabaaba\textvisiblespace}\]
|
||
|
|
il serait possible de former queque chose qui ressemble à des phrases en plaçant ces mots les uns à côté des autres. Cette opération se nomme la concaténation et on la note par un point. Ainsi, on va formellement définir la concaténation ainsi :
|
||
|
|
\[\text{Soit m et n }\in \Sigma^*\text{\hspace{0.3cm} Alors, m.n=mn}\]
|
||
|
|
On peut ainsi tenter de reproduire l'apparence formelle d'un langage par concaténation des mots ci-dessus (en s'imaginant un espace invisible) :
|
||
|
|
\[\text{abaab\textvisiblespace}.\text{aba\textvisiblespace}.\text{aabaaba\textvisiblespace}=\text{abaab aba aabaaba}\]
|
||
|
|
Certes, le résultat ne correspond qu'en apparence à un langage. Mais, l'alphabet est très restreint.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
De manière naturelle, on va donc définir la notion de langage comme un sous-ensemble de l'ensemble de tous les mots d'un alphabet donné. Un langage est donc un ensemble de mots. On peut donc faire l'union, l'intersection, \dots de deux langages.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
L'exemple classique est le langage des expressions arithmétiques. Il est défini à partir de l'alphabet suivant :
|
||
|
|
\[\Sigma = \{0,1,2,3,4,5,6,7,8,9,+,-,*,/\}\]
|
||
|
|
Le langage des expressions arithmétiques s'écrit alors :
|
||
|
|
\[L(\text{expr. arithm.})=\{\dots ,342, 34+4, 45+34, 2=4, \dots\}\]
|
||
|
|
Relevez qu'il ne s'agit pas de l'ensemble de tous les mots formé sur l'alphabet, mais d'un sous ensemble qui ne contient pas l'expression 34+++43==, par exemple. Évidemment, il faut spécifier comment on réalise le choix de chaque expression.
|
||
|
|
|
||
|
|
\begin{ex}
|
||
|
|
Sur l'alphabet des chiffres binaires (que vous noterez précisément), donnez le langage \(L\) des nombres à trois chiffres.
|
||
|
|
\begin{sol}
|
||
|
|
L'alphabet des chiffres binaires est : \(\Sigma=\{0,1\}\) et le langage des nombres binaires à trois chiffres est :
|
||
|
|
\[\Sigma^*=\{000,001,010,011,100,101,110,111\}\]
|
||
|
|
\end{sol}
|
||
|
|
\end{ex}
|
||
|
|
|
||
|
|
\begin{ex}\label{codons}
|
||
|
|
Pour la molécule d'ADN, définissez un alphabet de ses composants et déterminez quelques éléments du langage des \emph{codons}, acide aminé constitué de triplets de nucléotides. Combien peut-il y en avoir si leur arrangement tient compte de l'ordre et qu'il peut y avoir des répétitions.
|
||
|
|
|
||
|
|
Indication : les nucléotides sont les briques de base de l'ADN.
|
||
|
|
\begin{sol}
|
||
|
|
En considérant les quatre nucléotides composant l'ADN, la thymine (T), la cytosine (C), l'adénine (A) et la guanine (G), on peut définir l'alphabet nécessaire ainsi :
|
||
|
|
\[\Sigma=\{A,C,G,T\}\]
|
||
|
|
Les codons sont quant à eux des ensemble de trois nucléotides, pris parmi les quatre disponibles dans l'alphabet. Le langage ainsi formé est :
|
||
|
|
\[L=\{AAC,ACT,ACT,CTG,GTC, \dots\}\]
|
||
|
|
et la combinatoire donne pour un arrangement avec répétition de trois éléments pris parmi quatre :
|
||
|
|
\[\overline{A_3^4}=4^3=64\;\text{possibilités}\]
|
||
|
|
\end{sol}
|
||
|
|
\end{ex}
|
||
|
|
|
||
|
|
\bigskip
|
||
|
|
La génération ou la vérification des expressions valables pour un langage donné peut se faire de différentes manières. Nous allons présenter dans la section suivante les moyens qui nous permettrons de décrire simplement des langages particuliers. On peut utiliser pour cela soit un automate soit une expression régulière.
|
||
|
|
|
||
|
|
\section{Langage rationnel}
|
||
|
|
|
||
|
|
\subsection{Les automates}
|
||
|
|
|
||
|
|
Une manière particulièrement compréhensible de tester l'appartenance d'une expression à un langage est d'utiliser un automate. Il s'agit d'une sorte de machine symbolique capable de générer un ensemble de mots. On la suit dans la construction de ceux-ci selon des flèches qui mènent d'un état à l'autre par la concaténation successive de certaines mots de l'alphabet. Pour des raison de compréhension, on va commencer par donner un exemple d'automate à travers une représentation graphique qui fait correspondre des ronds aux états et des flèches aux éléments de l'alphabet. Un état initial est un rond sur lequel arrive une flèche vide et un état final est constitué d'un double cercle. Ainsi, on représente un automate reconnaissant le mot :
|
||
|
|
\[aba\;\text{ sur l'alphabet }\;\Sigma=\{a,b\}\]
|
||
|
|
par la figure suivante :
|
||
|
|
\begin{center}
|
||
|
|
\begin{postscript}
|
||
|
|
\VCDraw{%
|
||
|
|
\begin{VCPicture}{(0,-2)(9,0)}
|
||
|
|
% states
|
||
|
|
\State{(0,0)}{A} \State{(3,0)}{B} \State{(6,0)}{C} \FinalState{(9,0)}{D}
|
||
|
|
% initial--final
|
||
|
|
\Initial{A}
|
||
|
|
% transitions
|
||
|
|
\EdgeL{A}{B}{a} \EdgeL{B}{C}{b} \EdgeL{C}{D}{a}
|
||
|
|
%
|
||
|
|
\end{VCPicture}}
|
||
|
|
\end{postscript}
|
||
|
|
\end{center}
|
||
|
|
Relevons qu'il est possible de considérer l'unique mot construit par cet automate comme un langage qu'on peut définir mathématiquement très simplement par :
|
||
|
|
\[L=\{m\in\Sigma^*\,|\,m=aba\}\]
|
||
|
|
|
||
|
|
où la barre verticale \(|\) signifie ``tel que''.
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Évidemment, l'objectif est de permettre la construction de langages plus étendus. On peut par exemple construire le langage constitué d'une séquence de ab ainsi :
|
||
|
|
\begin{center}
|
||
|
|
\begin{postscript}
|
||
|
|
\VCDraw{%
|
||
|
|
\begin{VCPicture}{(0,-1)(3,1)}
|
||
|
|
% states
|
||
|
|
\FinalState{(0,0)}{A} \State{(3,0)}{B}
|
||
|
|
% initial--final
|
||
|
|
\Initial{A}
|
||
|
|
% transitions
|
||
|
|
\ArcL{A}{B}{a} \ArcL{B}{A}{b}
|
||
|
|
%
|
||
|
|
\end{VCPicture}}
|
||
|
|
\end{postscript}
|
||
|
|
\end{center}
|
||
|
|
|
||
|
|
Cet exemple permet d'engendrer une infinité de mots du type ab, abab, ababab, \dots
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Par ailleurs, la présence d'un état initial, simultanément final, implique l'existence dans le langage d'un mot vide noté \(\epsilon\). On écrira donc mathématiquement le langage ainsi :
|
||
|
|
\[L=\{m\in\Sigma^*\,|\,m=\epsilon,ab,abab,ababab,\dots\}\]
|
||
|
|
|
||
|
|
Un dernier exemple montre qu'il est possible de générer des langages bien plus complexes. Sans dire immédiatement ce dont il s'agit, voici l'automate :
|
||
|
|
|
||
|
|
\begin{center}
|
||
|
|
\begin{postscript}
|
||
|
|
\VCDraw{%
|
||
|
|
\begin{VCPicture}{(0,-1)(6,2)}
|
||
|
|
% states
|
||
|
|
\State{(0,0)}{A} \State{(3,0)}{B} \StateLineDouble \State{(6,0)}{C}
|
||
|
|
% initial--final
|
||
|
|
\Initial{A}
|
||
|
|
% transitions
|
||
|
|
\EdgeL{A}{B}{a} \ArcL{B}{C}{b} \ArcL{C}{B}{b}
|
||
|
|
\LoopN{A}{a}
|
||
|
|
%
|
||
|
|
\end{VCPicture}}
|
||
|
|
\end{postscript}
|
||
|
|
\end{center}
|
||
|
|
|
||
|
|
Le langage reconnu est constitué de mots comprenant en premier lieu au moins un a, suivi par un nombre impair de b. On peut aussi écrire :
|
||
|
|
\[L=\{m\in\Sigma^*\,|\,m=a^nb^m,\,n\in\mathbb{N}^*\,\text{et}\;m=2\cdot k+1,\,k\in\mathbb{N}\}\]
|
||
|
|
où \(\mathbb{N}^*\) est l'ensemble des nombres entiers positifs sans le zéro et \(\mathbb{N}\) celui avec le zéro.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
En conclusion, on peut définir un automate de manière générale comme un ensemble constitué
|
||
|
|
\begin{itemize}
|
||
|
|
\item d'un alphabet \(\Sigma\),
|
||
|
|
\item d'un ensemble fini d'état, généralement noté \(E\),
|
||
|
|
\item d'un ensemble d'état initiaux \(I\) tel que \(I\subseteq E\),
|
||
|
|
\item d'un ensemble d'état finaux \(F\) tel que \(F\subseteq E\) et
|
||
|
|
\item d'une fonction de transition \[\delta:E\times\Sigma\longrightarrow E\]
|
||
|
|
\end{itemize}
|
||
|
|
|
||
|
|
Où le signe \(\subseteq\) signifie ``appartient à''.
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Le dernier point de cette définition mérite des explications. La représentation graphique des automates donnée ci-dessus met clairement en évidence les transitions (flèches) entre états. Celle-ci doivent aussi trouver une expression mathématique. C'est la fonction de transition.
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Reprenons le dernier exemple d'automate donné ci-dessus. Considérons chacun des points permettant de le définir mathématiquement.
|
||
|
|
|
||
|
|
L'alphabet tout d'abord est clairement donné par \(\Sigma=\{a,b\}\).
|
||
|
|
|
||
|
|
L'ensemble des états est \(E=\{e_1,e_2,e_3\}\) et on peut en donner une représentation légèrement plus complète :
|
||
|
|
|
||
|
|
\begin{center}
|
||
|
|
\begin{postscript}
|
||
|
|
\VCDraw{%
|
||
|
|
\begin{VCPicture}{(0,-1)(6,2)}
|
||
|
|
% states
|
||
|
|
\State[e_1]{(0,0)}{A} \State[e_2]{(3,0)}{B} \StateLineDouble \State[e_3]{(6,0)}{C}
|
||
|
|
% initial--final
|
||
|
|
\Initial{A}
|
||
|
|
% transitions
|
||
|
|
\EdgeL{A}{B}{a} \ArcL{B}{C}{b} \ArcL{C}{B}{b}
|
||
|
|
\LoopN{A}{a}
|
||
|
|
%
|
||
|
|
\end{VCPicture}}
|
||
|
|
\end{postscript}
|
||
|
|
\end{center}
|
||
|
|
|
||
|
|
L'ensemble des états initiaux se résume à \(I=\{e_1\}\) et celui des états finaux à \(F=\{e_3\}\).
|
||
|
|
|
||
|
|
La fonction de transition \(\delta\) est alors donnée par :
|
||
|
|
\begin{align*}
|
||
|
|
\delta(e_1,a)&=e_1\,|\,e_2 & \delta(e_1,b)&=\perp\\
|
||
|
|
\delta(e_2,a)&=\perp & \delta(e_2,b)&=e_3\\
|
||
|
|
\delta(e_3,a)&=\perp & \delta(e_3,b)&=e_2
|
||
|
|
\end{align*}
|
||
|
|
où \(|\) signifie ``ou'' et \(\perp\) signifie ``indéfini''.
|
||
|
|
|
||
|
|
\bigskip
|
||
|
|
Ce dernier exemple est aussi intéressant du point de vue du déterminisme du résultat. La fonction de transition \(\delta(e_1,a)\) donne deux solution possibles : \(e_1\) ou \(e_2\). Cela signifie qu'à partir de l'état \(e_1\), par la transition \(a\), un choix non déterminé peut avoir lieu. L'automate est alors dit \emph{non déterministe}. Cela peut constituer un problème et il est possible de le rendre déterministe. Mais nous n'aborderons pas ce point dans ce cours. Il convenait cependant de le mentionner.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Nous avons vu dans ce paragraphe une manière de \emph{reconnaître} mécaniquement un langage simplement formé de mots issus d'un alphabet à l'aide d'un automate. Nous avons vu deux manières de représenter celui-ci, par un diagramme et mathématiquement. Chacune de ces deux expressions constitue un mode de représentation qui a des avantages et des inconvénients. Les automates soulignent clairement le caractère mécanique du processus de reconnaissance. L'expression mathématique exprime quant à elle mieux les propriétés ensemblistes et relationnelles de la notion d'automate.
|
||
|
|
|
||
|
|
\begin{ex}\label{autosimple}
|
||
|
|
Construisez un automate sur l'alphabet \(\Sigma=\{a,b\}\) qui reconnaît les mots suivants : aba, aab, abb et bbb.
|
||
|
|
\begin{sol}
|
||
|
|
Il s'agit d'un automate simple sans grande difficultés. Il est déterministe puisque de chaque état ne part qu'une seule transition de même type.
|
||
|
|
\begin{center}
|
||
|
|
\begin{postscript}
|
||
|
|
\VCDraw{%
|
||
|
|
\begin{VCPicture}{(0,-2)(6,4)}
|
||
|
|
% states
|
||
|
|
\State[e_1]{(0,0)}{A} \State[e_2]{(2,1)}{B} \State[e_3]{(4,1)}{C}
|
||
|
|
\State[e_5]{(4,3)}{E}
|
||
|
|
\State[e_8]{(2,-1)}{G} \State[e_9]{(4,-1)}{H}
|
||
|
|
\StateLineDouble \State[e_{10}]{(6,-1)}{I} \State[e_4]{(6,1)}{D} \State[e_6]{(6,3)}{F}
|
||
|
|
% initial--final
|
||
|
|
\Initial{A}
|
||
|
|
% transitions
|
||
|
|
\EdgeL{A}{B}{a} \EdgeL{B}{C}{a} \EdgeL{C}{D}{b}
|
||
|
|
\EdgeL{B}{E}{b} \EdgeL{E}{F}{b}
|
||
|
|
\EdgeL{A}{G}{b} \EdgeL{G}{H}{b} \EdgeL{H}{I}{b}
|
||
|
|
%
|
||
|
|
\end{VCPicture}}
|
||
|
|
\end{postscript}
|
||
|
|
\end{center}
|
||
|
|
\end{sol}
|
||
|
|
\end{ex}
|
||
|
|
|
||
|
|
\begin{ex}
|
||
|
|
Construisez un automate qui reconnaisse la succession des feux de circulation rouge-jaune-vert, allumé successivement et indéfiniment dans cet ordre.
|
||
|
|
\begin{sol}
|
||
|
|
Le problème peut sembler complexe car l'énoncé du mot allumé fait immédiatement penser à éteint. Naturellement, on pense à un état allumé et à un autre éteint. Comme il y a trois couleurs, on s'imagine alors six états et leur représentation avec des transitions du type ``s'allume'' ou ``s'éteint'' ne va pas de soit.
|
||
|
|
|
||
|
|
Pour s'en sortir simplement, il faut au contraire penser ``quel est la couleur du feu''. Cela suppose qu'on ne considère que l'état allumé du feu. On peut alors dire rouge, puis jaune, puis vert, puis rouge, \dots On pourrait aussi dire, c'est le rouge qui s'allume, puis c'est le jaune qui s'allume, puis \dots Cela nous permet alors de représenter la succession des états allumé du feu par :
|
||
|
|
\begin{center}
|
||
|
|
\begin{postscript}
|
||
|
|
\VCDraw{%
|
||
|
|
\begin{VCPicture}{(0,-3)(11,1)}
|
||
|
|
% states
|
||
|
|
\State[r]{(0,0)}{A} \State[j]{(4,0)}{B} \State[v]{(2,-2)}{C}
|
||
|
|
\State{(7,0)}{D} \State{(11,0)}{E} \State{(9,-2)}{F}
|
||
|
|
% initial--final
|
||
|
|
\Initial{A} \Initial{D}
|
||
|
|
% transitions
|
||
|
|
\EdgeL{A}{B}{} \EdgeR{B}{C}{} \EdgeR{C}{A}{}
|
||
|
|
\EdgeL{D}{E}{r} \EdgeR{E}{F}{j} \EdgeR{F}{D}{v}
|
||
|
|
%
|
||
|
|
\end{VCPicture}}
|
||
|
|
\end{postscript}
|
||
|
|
\end{center}
|
||
|
|
En particulier, l'automate ci-dessus permet la reconnaissance de la chaîne de caractère rjvrjvrjv\dots{} qui est une représentation de la succession des couleurs (allumées) du feu de circulation.
|
||
|
|
\end{sol}
|
||
|
|
\end{ex}
|
||
|
|
|
||
|
|
\begin{ex}
|
||
|
|
Construisez un automate qui reconnaisse les codons de l'exercice \ref{codons}.
|
||
|
|
\begin{sol}
|
||
|
|
On a vu qu'il y a 64 possibilités pour former un acide aminé constitué d'un triplet choisi parmi quatre nucléotides. Il peut sembler alors que l'automate correspondant doive être très complexe. Mais au contraire, en raison du fait qu'on peut mettre n'importe quel nucléotide à chaque place parmi les trois disponibles nous permet de constituer un automate particulièrement simple :
|
||
|
|
\begin{center}
|
||
|
|
\begin{postscript}
|
||
|
|
\VCDraw{%
|
||
|
|
\begin{VCPicture}{(0,-1)(8,1)}
|
||
|
|
% states
|
||
|
|
\State{(0,0)}{A} \State{(4,0)}{B} \State{(8,0)}{C}
|
||
|
|
\StateLineDouble \State{(12,0)}{D}
|
||
|
|
% initial--final
|
||
|
|
\Initial{A}
|
||
|
|
% transitions
|
||
|
|
\EdgeL{A}{B}{C|G|T|U} \EdgeR{B}{C}{C|G|T|U} \EdgeR{C}{D}{C|G|T|U}
|
||
|
|
%
|
||
|
|
\end{VCPicture}}
|
||
|
|
\end{postscript}
|
||
|
|
\end{center}
|
||
|
|
où la notation C|G|T|U signifie soit C, soit G, soit T, soit U.
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
On constate ainsi la concision de la description de l'automate par rapport à l'exposé de tout les cas possibles.
|
||
|
|
\end{sol}
|
||
|
|
\end{ex}
|
||
|
|
|
||
|
|
\subsection{Les expressions rationnelles}
|
||
|
|
Voyons maintenant une autre manière de représenter les langages reconnus par les automates : les \emph{expressions rationnelles}\footnote{On parle aussi d'expressions régulières en raison de l'anglais \emph{regular expression}.}. Elles trouvent ici leur place pour souligner qu'il existe différentes approches dans la reconnaissance des langages (dits rationnels).
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Premièrement, une \emph{expression rationelle} est un mot. L'alphabet permettant de construire ce mot est particulier, puisque s'y trouve obligatoirement les symboles suivants : \((\,)\,+\,.\,*\,\emptyset\) Ainsi, on peut voir l'alphabet sur lequel on construit les expressions rationelles comme composé de deux ensemble : un alphabet \(\Sigma\) choisi selon les besoins et l'ensemble des symboles donné ci-dessus. L'alphabet des expressions rationelles est donc formellement :
|
||
|
|
\[\Sigma^{\text{expressions rationnelles}}=\Sigma \cup \{(,),+,.,^*,\varepsilon\}\]
|
||
|
|
où \(\varepsilon\) est le caractère vide.
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Secondement, une expression rationnelle doit obéir à une \emph{syntaxe}. Une manière de construire un langage, en tant que partie de l'ensemble des mots de \(\Sigma\), est de le faire à partir d'un automate. Une autre manière est de le faire à partir d'un ensemble d'opération qui permettent de le définir complètement. On appelle ces opérations des règles de \emph{syntaxe}. En d'autre termes, ces règles autorisent ou interdisent la production de mot particuliers sans référence au sens des mots produits. Ainsi, si e et r sont des expressions rationnelle, alors il faut ajouter que les règles de syntaxe des expressions rationnelles autorisent les trois expressions (e+r), (e.r) et (e*) comme expressions rationnelles. On dit ici simplement que les trois suites de caractères précédentes sont correctement formées pour qu'il s'agisse d'expressions rationnelles. Le sens des symboles +, . et * n'est pas précisé car il ne s'agit que de règles de syntaxe.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
En définitive donc, on peut définir l'ensemble des expressions rationnelles par une règle de base (B) et par un règle récursive (R) :
|
||
|
|
\begin{description}
|
||
|
|
\item[B.] \(\varepsilon\) et e avec \(\text{e}\in \Sigma\) sont des mots sur \(\Sigma \cup \{(,),+,.,^*,\varepsilon\}\)
|
||
|
|
\item[R.] si e et r sont des expressions rationnelles, alors (e+r), (e.r) et (e*) le sont aussi.
|
||
|
|
\end{description}
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Voilà l'ensemble des expressions rationnelles correctement défini. Il s'agit d'une définitions complexe sur laquelle nous ne reviendrons pas dans le cadre de ce cours. Il faut cependant retenir l'idée de syntaxe comme règles de production d'expressions. Elle nous mènera plus tard à celle de grammaire.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Jusqu'à présent nous n'avons pas parlé de sémantique. La définition rigoureuse du sens des symboles utilisés précédemment pour les expressions rationnelles (\(+,.,*\)) passe par la construction d'une relation de l'ensemble des expressions rationnelle sur une partie de l'ensemble des mots. Ces symboles prennent alors une signification particulière : le \(+\) devient un ou (\(\cup\) ou \(|\)), le \(.\) une concaténation de deux expressions rationnelles et l'étoile devient la répétition de zéro ou plusieurs fois le caractère précédent.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Ainsi, en imaginant la reconnaissance du code postal d'une ville suisse constitués de quatre chiffres, on peut écrire une expression rationnelle qui exprime cette structure de la manière suivante :
|
||
|
|
\[(0|1|2|3|4|5|6|7|8|9).(0|1|2|3|4|5|6|7|8|9).(0|1|2|3|4|5|6|7|8|9).(0|1|2|3|4|5|6|7|8|9)\]
|
||
|
|
Évidemment, cette notation n'est pas très pratique et en réalité on définit d'autres symboles qui permettent d'alléger l'écriture. Par exemple, de manière évidente :
|
||
|
|
\[[0..9]\{4\}\]
|
||
|
|
On trouvera avec \cite{DB08} un ouvrage très complet sur la syntaxe et la signification des symboles les plus utilisés.
|
||
|
|
|
||
|
|
\begin{ex}\label{autotomate}
|
||
|
|
Exprimez l'automate suivant en français et transformez-le en expression rationnelle.
|
||
|
|
\begin{center}
|
||
|
|
\begin{postscript}
|
||
|
|
\VCDraw{%
|
||
|
|
\begin{VCPicture}{(0,-1)(4,1)}
|
||
|
|
% states
|
||
|
|
\State[e_1]{(4,0)}{B}
|
||
|
|
\StateLineDouble \State[e_0]{(0,0)}{A}
|
||
|
|
% initial--final
|
||
|
|
\Initial{A}
|
||
|
|
% transitions
|
||
|
|
\ArcL{A}{B}{b} \ArcL{B}{A}{a} \LoopE{B}{b}
|
||
|
|
%
|
||
|
|
\end{VCPicture}}
|
||
|
|
\end{postscript}
|
||
|
|
\end{center}
|
||
|
|
\begin{sol}
|
||
|
|
On doit tout d'abord faire un b, puis un nombre quelconque (voir nul) de b. Comme l'état de droite n'est pas final, il faut ensuite revenir à celui de gauche par un a. Enfin, on peut faire tout cela un nombre quelconque de fois, y compris aucune. L'expression rationnelle correspondante est :
|
||
|
|
\[(bb^*a)^*\]
|
||
|
|
\end{sol}
|
||
|
|
\end{ex}
|
||
|
|
|
||
|
|
\begin{ex}
|
||
|
|
Construisez l'expression régulière correspondant aux numéros de plaques minéralogiques suisses : deux lettres, suivies de cinq chiffres décimaux.
|
||
|
|
\begin{sol}
|
||
|
|
De manière très naturelle, on a :
|
||
|
|
\[[A..Z]\{2\}[0..9]\{5\}\]
|
||
|
|
\end{sol}
|
||
|
|
\end{ex}
|
||
|
|
|
||
|
|
\begin{ex}
|
||
|
|
Construisez l'expression régulière correspondant à l'automate de l'exercice \ref{autosimple}.
|
||
|
|
\begin{sol}
|
||
|
|
Il faut raisonner à partir de la dernière transition avant l'état final. Il s'agit toujours d'une transition b. Donc, l'expression régulière finira par un b. Puis, on a soit deux b, soit un a suivi d'un a ou b. Cela se traduit par :
|
||
|
|
\[(bb|a(a|b))b\]
|
||
|
|
\end{sol}
|
||
|
|
\end{ex}
|
||
|
|
|
||
|
|
\section{Langage de Lindenmayer}
|
||
|
|
Avant de nous intéresser aux langages de Lindenmayer, dit L-system, il faut pousser un peu plus avant l'étude des langages formels.
|
||
|
|
|
||
|
|
On a vu plusieurs manières de formaliser un langage simple. La formalisation des expressions rationnelles, par exemple, a fait apparaître des règles de syntaxe qui évoquent une \emph{grammaire}. Il est intéressant ici de préciser cette notion pour pouvoir formaliser au mieux les L-system.
|
||
|
|
|
||
|
|
\subsection{Grammaire}
|
||
|
|
Une \emph{grammaire} est un ensemble \(G\) d'objets tel que :
|
||
|
|
\begin{align*}
|
||
|
|
G=&\{T,N,R,S\}\text{ où : }\\
|
||
|
|
&T \text{ est l'alphabet des lettres terminales,}\\
|
||
|
|
&N\text{ est l'alphabet des lettres non terminales}\\
|
||
|
|
&S\in N\text{ est l'axiome}\\
|
||
|
|
&R\subseteq (T \cup N)^*\times(T \cup N)^*\text{ est un ensemble fini de règles de production.}
|
||
|
|
\end{align*}
|
||
|
|
Une convention pratique veut que les symboles non-terminaux s'écrivent en majuscule et les terminaux en minuscule.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Voici un exemple simple, mais assez complet.
|
||
|
|
\begin{align*}
|
||
|
|
G=&\{T,N,R,S\}\text{ où : }\\
|
||
|
|
&T=\{a,b,m,n\}\\
|
||
|
|
&N=\{O,P\}\\
|
||
|
|
&S=aO\\
|
||
|
|
&R=\{O\rightarrow aO|bP\;\text{ et }\;P\rightarrow m|n\}
|
||
|
|
\end{align*}
|
||
|
|
où le signe \(|\) signifie ou.
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
On peut donner deux exemples de génération d'éléments à partir de cette grammaire :
|
||
|
|
\begin{enumerate}
|
||
|
|
\item \(aO\rightarrow aaO\rightarrow aaaO\rightarrow aaabP\rightarrow aaabn\)
|
||
|
|
\item \(aO\rightarrow aaO\rightarrow aabP\rightarrow aabm\)
|
||
|
|
\end{enumerate}
|
||
|
|
On comprend aisément le rôle des règles de productions et celui des lettres terminales qui vont arrêter la génération de la chaîne de caractère.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Un automate peut constituer un autre exemple intéressant. En effet, il est possible de traduire un automate par une grammaire appropriée.
|
||
|
|
\begin{align*}
|
||
|
|
G=&\{T,N,R,S\}\text{ où : }\\
|
||
|
|
&T=\{\text{états terminaux}\}\\
|
||
|
|
&N=\{\text{états non terminaux}\}\\
|
||
|
|
&S=\text{état initial}\\
|
||
|
|
&R=\{\text{fonction de transition}\}
|
||
|
|
\end{align*}
|
||
|
|
Pour plus de clarté, considérons l'automate de l'exercice \ref{autotomate} et tentons de le traduire en une grammaire.
|
||
|
|
\begin{align*}
|
||
|
|
G=&\{T,N,R,S\}\text{ où : }\\
|
||
|
|
&T=\{e_0\}\\
|
||
|
|
&N=\{e_1\}\\
|
||
|
|
&S=e_0\\
|
||
|
|
&R=\{\delta(e_0,a)=\bot\;;\;\delta(e_0,b)=e_1\;;\;\delta(e_1,a)=e_0\;;\;\delta(e_1,b)=e_1\}
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Évidemment, l'existence d'une correspondance entre automate et expression régulière implique l'idée d'une formalisation des expressions régulières sous forme de grammaire. Nous n'aborderons pas ce cas ici.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Enfin, voici un autre exemple de grammaire où il n'y a pas de symbole terminaux.
|
||
|
|
\begin{align}\label{grammaire_algue_de_lindenmayer}
|
||
|
|
G=&\{T,N,R,S\}\text{ où : }\\\nonumber
|
||
|
|
&T=\emptyset\\\nonumber
|
||
|
|
&N=\{A,B\}\\\nonumber
|
||
|
|
&S=A\\\nonumber
|
||
|
|
&R=\{A\rightarrow AB\;\text{ et }\;B\rightarrow A\}
|
||
|
|
\end{align}
|
||
|
|
Celle-ci permet la génération de séquences infinies dont nous allons parler maintenant.
|
||
|
|
|
||
|
|
\subsection{Génération de séquence}
|
||
|
|
La production des éléments de la grammaire donnée dans le dernier exemple ci-dessus débute par l'axiome \(A\). Ensuite, les deux règles de productions doivent être utilisées pour produire l'élément suivant : remplacer \(A\) par \(AB\) et \(B\) par \(A\). Comme il n'y a qu'un \(A\) dans l'axiome, seule la première règle s'applique tout d'abord et on obtient \(AB\). Puis, les deux règles doivent à nouveau être utilisées à partir de cet état pour produire le suivant. On remplace donc les \(A\) par \(AB\) et \(B\) par \(A\) pour chaque lettre de \(AB\). On obtient ainsi \(ABA\). Et on continue indéfiniment. On obtient alors :
|
||
|
|
\begin{align}\label{chaine_algue_de_lindenmayer}
|
||
|
|
A&\nonumber\\A&B\nonumber\\A&BA\nonumber\\A&BAAB\nonumber\\A&BAABABA\nonumber\\A&BAABABAABAAB
|
||
|
|
\end{align}
|
||
|
|
Ces chaînes n'ont pas encore de signification. Mais on peut déjà envisager différentes règles de productions permettant de gérérer de multiples chaines de caractères. Beaucoup de questions peuvent alors se poser concernant les propriétés des chaines ainsi générées.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Voici enfin un autre exemple très connu de grammaire permettant de générer des chaînes auxquelles on peut attacher une signification par interprétation graphique :
|
||
|
|
\begin{align}\label{grammaire_courbe_de_koch}
|
||
|
|
G=&\{T,N,R,S\}\text{ où : }\\\nonumber
|
||
|
|
&T=\{+,-\}\\\nonumber
|
||
|
|
&N=\{F\}\\\nonumber
|
||
|
|
&S=F\\\nonumber
|
||
|
|
&R=\{F\rightarrow F+F-F-F+F\}
|
||
|
|
\end{align}
|
||
|
|
Notez la séparation entre les symboles terminaux, sans règles de production et le symbole non terminal auquel correspond une règle de production.
|
||
|
|
|
||
|
|
La génération des chaines est alors la suivante :
|
||
|
|
\begin{align}\label{chaine_courbe_de_koch}
|
||
|
|
F&\nonumber\\F&+F-F-F+F\nonumber\\F&+F-F-F+F+F+F-F-F+F-F+F-F-\;\hookleftarrow\nonumber\\\hookrightarrow\;&F+F-F+F-F-F+F+F+F-F-F+F
|
||
|
|
\end{align}
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Encore une fois, le sens de ces chaines n'est pas encore évident. Par ailleurs, on voit aussi que la génération des caractères de ces chaines devient très vite inaccessible au possibilités humaines en raison du nombre élevé de caractères produits. Une mécanisation de la production est donc rapidement nécessaire.
|
||
|
|
|
||
|
|
\subsection{L-system}
|
||
|
|
Les deux derniers exemples ci-dessus ((\ref{grammaire_courbe_de_koch}) et (\ref{grammaire_algue_de_lindenmayer})) sont des systèmes de Lindenmayer ou L-system. De quoi s'agit-il ? L'ouvrage de référence en la matière, \emph{The Algorithmic Beauty of Plants} \cite[p.2-3]{LA04}, en présente le contexte en ces termes :
|
||
|
|
|
||
|
|
\begin{quotation}
|
||
|
|
\og \selectlanguage{english}In 1968 a biologist, Aristid Lindenmayer, introduced a new type of string-rewriting mechanism, subsequently termed L-systems. The essential difference between Chomsky grammars and L-systems lies in the method of applying productions. In Chomsky grammars productions are applied sequentially, whereas in L-systems they are applied in parallel and simultaneously replace all letters in a given word. This difference reflects the biological motivation of L-systems. Productions are intended to capture cell divisions in multicellular organisms, where many divisions may occur at the same time. Parallel production application has an essential impact on the formal properties of rewriting systems.\selectlanguage{french}\fg
|
||
|
|
\end{quotation}
|
||
|
|
|
||
|
|
L'objectif est donc de modéliser des mécanisme de division (cellulaire). Le moyen utilisé est un mécanisme de réécriture. Quoi de plus naturel donc que d'utiliser une grammaire précisément basée sur la réécriture. Les règles de production s'y prètent bien et les deux exemples présentés ci-dessus en sont une belle démonstration. Il ne s'agit pas ici d'une division cellulaire, mais de la réplication d'un motif sur lui-même. Une grammaire en est ici l'origine et nous verrons par la suite qu'elle peut se traduire par une récursivité des algorithmes nécessaires pour la production de modifs conséquents.
|
||
|
|
|
||
|
|
Mais, pour bien comprendre la signification des mécanismes de production des L-system dans la réalité, il faut maintenant en donner une interpréation graphique.
|
||
|
|
|
||
|
|
\subsection{Interprétation graphique}
|
||
|
|
Il s'agit ici d'utiliser les chaines de caractères produites par les grammaires pour en faire une représentation graphique. L'articulation d'un mécanisme de production général et d'une analyse des briques composant les structures végétales est certainement à l'origine de cette idée. Elle a trouvé son expression complète grace aux possibilités de dessin proposés par le langage de programmation Logo et la tortue qui lui est attachée.
|
||
|
|
|
||
|
|
L'interprétation consiste à utiliser les caractères de l'ensemble terminal \(N\) comme des instructions d'orientation de la tortue et les symboles non-terminaux comme des instruction de construction du chemin. Classiquement, on a :
|
||
|
|
|
||
|
|
\begin{description}
|
||
|
|
\item[\(F\)] avancer d'un pas en avant,
|
||
|
|
\item[\(+\)] tourner à gauche d'un angle donné,
|
||
|
|
\item[\(-\)] tourner à droite d'un angle donné.
|
||
|
|
\end{description}
|
||
|
|
|
||
|
|
Cette interprétation permet de suivre les chaines de caractères produites par la grammaire pour en tracer une représentation graphique.
|
||
|
|
|
||
|
|
\subsubsection{Koch}
|
||
|
|
L'exemple donné par la grammaire (\ref{grammaire_courbe_de_koch}), correspondant aux chaines (\ref{chaine_courbe_de_koch}) peut ainsi prendre l'apparence des figures \ref{figkoch} pour un angle de 90\textdegree.
|
||
|
|
|
||
|
|
\begin{figure*}[t]
|
||
|
|
\centering
|
||
|
|
\subfigure[F+F-F-F+F\label{figkoch1}]{\includegraphics{koch1.eps}}\qquad
|
||
|
|
\subfigure[F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F\label{figkoch2}]{\includegraphics{koch2.eps}}\\
|
||
|
|
\subfigure[Plus encore ...\label{figkoch3}]{\includegraphics[width=8cm]{koch3.eps}}
|
||
|
|
\caption{La courbe de Koch\label{figkoch}}
|
||
|
|
\end{figure*}
|
||
|
|
|
||
|
|
La figure \ref{figkoch1} permet de suivre l'interprétation graphique à la main, caractère après caractère. Mais, on hésite déjà à le faire à la figure suivante pour des raisons évidentes.
|
||
|
|
|
||
|
|
A part l'esthétique des figures \ref{figkoch}, cette interprétation graphique semble ne pas apporter grand chose. Pourtant, les objets étudiés dans \emph{The Algorithmic Beauty
|
||
|
|
of Plants
|
||
|
|
} \cite[p.8-9]{LA04} et reproduits\footnote{Le code permettant d'obtenir ces structures sera présenté plus loin.} dans la figure \ref{figkochisland} sont déjà plus intéressants et montrent des structures qui commencent à ressembler vaguement à des cristaux par exemple.
|
||
|
|
|
||
|
|
\begin{figure*}[ht]
|
||
|
|
\centering
|
||
|
|
\subfigure[F-F+F+FF-F-F+F (axiome F-F-F-F)\label{figkochisland1}]{\includegraphics{kochIsland1.eps}}\qquad
|
||
|
|
\subfigure[F-F+F+FF-F-F+F (axiome F-F-F-F)\label{figkochisland2}]{\includegraphics[width=5cm]{kochIsland2.eps}}\\
|
||
|
|
\subfigure[F+FF-FF-F-F+F+FF-F-F+F+FF+FF-F (axiome F-F-F-F)\label{figkochislandquadratic2}]{\includegraphics[width=5cm]{kochIslandquadratic2.eps}}
|
||
|
|
\caption{Une autre courbe de Koch\label{figkochisland}}
|
||
|
|
\end{figure*}
|
||
|
|
|
||
|
|
\subsubsection{Modélisation des plantes}
|
||
|
|
Un autre exemple d'utilisation d'une grammaire interprétée de manière particulière est donné par la modélisation de la croissance des plantes. Turtle est ici utilisé comme précédemment. Mais l'alphabet est étendu par deux nouveaux signes : les crochets [ et ]. Leur signification dans le cadre de Turtle est spéciale :
|
||
|
|
\begin{description}
|
||
|
|
\item[le crochet ouvrant] [ signifie qu'il faut mémoriser la position et la direction courante de la tortue et
|
||
|
|
\item[le crochet fermant] ] signifie qu'il faut faire revenir la tortue à la position et direction précédemment mémorisée.
|
||
|
|
\end{description}
|
||
|
|
Cette opération de mémorisation est nécessaire pour permettre une structure d'arbre qui n'est pas possible sans cela puisque le parcours de la tortue est alors continu.
|
||
|
|
|
||
|
|
Voyons-en un exemple d'une telle grammaire.
|
||
|
|
\begin{align}\label{grammaire_plante}
|
||
|
|
G=&\{T,N,R,S\}\text{ où : }\\\nonumber
|
||
|
|
&T=\{+,-,[,]\}\\\nonumber
|
||
|
|
&N=\{F\}\\\nonumber
|
||
|
|
&S=F\\\nonumber
|
||
|
|
&R=\{F\rightarrow F[+F]F[-F]F\}
|
||
|
|
\end{align}
|
||
|
|
|
||
|
|
Après deux fois l'application de la règle (deux générations), on obtient la chaîne suivante :
|
||
|
|
\begin{center}
|
||
|
|
F[+F]F[-F]F[+F[+F]F[-F]F]F[+F]F[-F]F[-F[+F]F[-F]F]F[+F]F[-F]F
|
||
|
|
\end{center}
|
||
|
|
Encore une fois, l'interprétation n'est pas triviale, pas plus que la programmation de la mémorisation.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Pourtant, la figure \ref{figplante} obtenue par l'interprétation graphique pour cinq génération et un angle de 25,7\textdegree{} est étonnante.
|
||
|
|
|
||
|
|
\begin{figure*}[t]
|
||
|
|
\centering
|
||
|
|
\includegraphics[width=12cm]{plante1.eps}
|
||
|
|
\caption{Modélisation d'une plante\label{figplante}}
|
||
|
|
\end{figure*}
|
||
|
|
|
||
|
|
Évidemment, on s'imagine bien que le remplacement récursif d'un même motif à partir de points clés de ce même motif mène à la construction d'arbre de ce type. Mais la figure produite est tout de même remarquable dans la structure ``botanique'' qu'elle présente, même si une tige aussi rectiligne est peu probable dans la réalité.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Plusieurs autres règles peuvent être utilisées. Plusieurs angles aussi. Comme présenté dans \emph{The Algorithmic Beauty of Plants} \cite[p.25]{LA04}, on obtient alors des structures dont la ressemblance avec des plantes réelles est étonnante. La figure \ref{figplantes} présente les ``plantes'' obtenues avec les règles suivantes :
|
||
|
|
\begin{align}
|
||
|
|
F &\rightarrow F[+F]F[-F]F\label{regle1}\\
|
||
|
|
F &\rightarrow FF-[-F+F+F]+[+F-F-F]\label{regle2}
|
||
|
|
\end{align}
|
||
|
|
|
||
|
|
\begin{figure*}[ht]
|
||
|
|
\centering
|
||
|
|
\subfigure[nbiteration = 5, angle = 20\textdegree{} (axiome F ; règle \ref{regle1})\label{figplante2}]{\includegraphics[width=10cm]{plante2.eps}}\\
|
||
|
|
\subfigure[nbiteration = 5, angle = 22,5\textdegree{} (axiome F ; règle \ref{regle2})\label{figplante3}]{\includegraphics[width=10cm]{plante3.eps}}
|
||
|
|
\caption{Deux autres plantes\label{figplantes}}
|
||
|
|
\end{figure*}
|
||
|
|
|
||
|
|
On peut aussi illustrer l'utilisation de plusieurs règles simultanément à travers les exemples \ref{regle3}, \ref{regle4} et \ref{regle5} où l'axiome est \(X\). Les deux règles sont appliquées successivement.
|
||
|
|
\begin{align}
|
||
|
|
X &\rightarrow F[+X]F[-X]+X\;\text{ et }\;F \rightarrow FF\label{regle3}\\
|
||
|
|
X &\rightarrow F[+X][-X]FX\;\text{ et }\;F \rightarrow FF\label{regle4}\\
|
||
|
|
X &\rightarrow F-[[X]+X]+F[+FX]-X\;\text{ et }\;F \rightarrow FF\label{regle5}
|
||
|
|
\end{align}
|
||
|
|
|
||
|
|
Le résultat de l'interprétation graphique est donné à la figure \ref{figplantes2}, page \pageref{figplante2}.
|
||
|
|
|
||
|
|
\begin{figure*}[ht]
|
||
|
|
\centering
|
||
|
|
\subfigure[nbiteration = 7, angle = 20\textdegree{} (axiome \ref{regle3})\label{figplante4}]{\includegraphics[width=6cm]{plante4.eps}}\qquad
|
||
|
|
\subfigure[nbiteration = 7, angle = 25,7\textdegree{} (axiome \ref{regle4})\label{figplante5}]{\includegraphics[width=6cm]{plante5.eps}}\\
|
||
|
|
\subfigure[nbiteration = 5, angle = 22,5\textdegree{} (axiome \ref{regle5})\label{figplante6}]{\includegraphics[width=8cm]{plante6.eps}}
|
||
|
|
\caption{Deux autres plantes\label{figplantes2}}
|
||
|
|
\end{figure*}
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Bien évidemment, ces exemples ne sont pas construits au hasard. Une étude approfondie de la forme des chaines nécessaires pour obtenir des structures réalistes de plantes doit être faite, ou tout au moins une réflection sur les motifs de base. On se reportera pour cela à l'adresse \url{http://algorithmicbotany.org/papers/} où sont présentés de nombreux exemples très crédibles. En ce qui nous concerne, l'objectif de ce petit cours n'étant pas d'étudier systèmatiquement ou de manière approfondie les plantes elles-même, on laisse au lecteur le soin de tenter de trouver des chaines crédibles et de les interpréter grâce à la programmation.
|
||
|
|
|
||
|
|
Car, il est temps maintenant de considérer cet aspect moins formel, mais aussi important dans le cadre d'un cours d'informatique. Nous allons donc commencer par considérer le problème de la création de L-system de manière algorithmique. Cela nous permettra d'avoir une bonne vision des mécanismes principaux permettant la génération de ces systèmes.
|
||
|
|
|
||
|
|
\subsection{Algorithmique\label{algo}}
|
||
|
|
|
||
|
|
\subsubsection{Création}
|
||
|
|
|
||
|
|
Commençons par la construction de la chaine de Lindenmayer. Nous avons vu que tout commence avec un axiome. Celui-ci peut être constitué de deux types de symboles : non-terminaux et terminaux. La production de la chaine consiste quant à elle à remplacer un certain nombre de fois les symboles non-terminaux par une chaine correspondante donné par une (ou plusieurs) règle. Pour simplifier la situation, on ne considérera ici qu'une seule règle. Il est donc nécessaire de disposer du nombre d'itération choisi, de l'axiome et de la règle qu'il faut initialiser. Ensuite viennent deux boucles. L'une pour répéter les remplacements des symboles non-terminaux par ceux de la règle et l'autre pour lire l'axiome. Finalement, au bout d'un nombre de génération donné, le résultat produit est un axiome ``final'' qui sera transmis pour interprétation graphique. L'algorithme \ref{algocreation}, page \pageref{algocreation}, traduit ce raisonnement en pseudo-code.
|
||
|
|
|
||
|
|
%\begin{comment}
|
||
|
|
%\begin{algorithm}[t]
|
||
|
|
%\caption{RRT}\label{algo_rrt}
|
||
|
|
%\begin{pseudocode}[ovalbox]{mystère}{a,b,c}
|
||
|
|
%a \PREND a+b\\
|
||
|
|
%c \PREND a+\sqrt{b}\\
|
||
|
|
%b \PREND a-b
|
||
|
|
%\end{pseudocode}
|
||
|
|
%\end{algorithm}
|
||
|
|
%\end{comment}
|
||
|
|
|
||
|
|
\begin{algorithm}[t]
|
||
|
|
\SetAlgoVlined
|
||
|
|
\SetAlgoCaptionSeparator{ \textendash}
|
||
|
|
%\SetAlCapSkip{5mm}
|
||
|
|
\Donnees{nbiteration, axiome, regle}
|
||
|
|
\Res{nouvel axiome}
|
||
|
|
initialisation\;
|
||
|
|
\Tq{on est < nbiteration}{
|
||
|
|
\Tq{on est < longueur de l'axiome}{
|
||
|
|
on lit un caractère de l'axiome\;
|
||
|
|
\Si{on trouve un caractère non terminal}{
|
||
|
|
on le remplace par la règle\;
|
||
|
|
}
|
||
|
|
\SinonSi{on trouve un caractère terminal}{
|
||
|
|
on le réécrit simplement\;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
\caption{Création de la chaine}\label{algocreation}
|
||
|
|
\end{algorithm}
|
||
|
|
|
||
|
|
\subsubsection{Interprétation}
|
||
|
|
|
||
|
|
Après la création de la chaine vient son interprétation. Pour cela, il est nécessaire de disposer de l'axiome ``final'', de la longueur choisie des segments produit par la tortue et de l'angle correspondant à chaque rotation. L'interprétation graphique se fait ensuite par la lecture de chaque caractères de la chaine et le lancement de l'opération correspondante par la tortue.
|
||
|
|
|
||
|
|
Si l'opération de mémorisation de la position de la tortue est simple, il faut analyser plus finement le retour à cette position. En effet, il est nécessaire de mémoriser plusieurs états différents avant d'y revenir successivement. Un tableau des états est donc nécessaire. De plus, une fois revenu sur un état mémorisé, il ne faut pas oublier de l'effacer. L'algorithme \ref{algointerpretation}, page \pageref{algointerpretation}, résume tout cela en pseudo-code.
|
||
|
|
|
||
|
|
\begin{algorithm}[bh]
|
||
|
|
\SetAlgoVlined
|
||
|
|
\SetAlgoCaptionSeparator{ \textendash}
|
||
|
|
%\SetAlCapSkip{5mm}
|
||
|
|
\Donnees{axiome, longueur, angle\\variable : tableau des états mémorisés}
|
||
|
|
\Res{le tracé}
|
||
|
|
initialisation\;
|
||
|
|
\Tq{on est < longueur de l'axiome}{
|
||
|
|
on lit un caractère de l'axiome\;
|
||
|
|
\Si{on trouve tel caractère}{
|
||
|
|
on demande à la tortue de faire telle opération\;
|
||
|
|
}
|
||
|
|
\SinonSi{on trouve tel autre caractère}{
|
||
|
|
on demande à la tortue de faire telle autre opération\;
|
||
|
|
}
|
||
|
|
\SinonSi{on trouve le caractère [}{
|
||
|
|
on mémorise sa position et sa direction
|
||
|
|
}
|
||
|
|
\SinonSi{on trouve le caractère ]}{
|
||
|
|
on récupère l'état, on y envoie la tortue et on efface cet état de la pile des état mémorisés
|
||
|
|
}
|
||
|
|
}
|
||
|
|
\caption{Interprétation graphique de la chaine}\label{algointerpretation}
|
||
|
|
\end{algorithm}
|
||
|
|
|
||
|
|
Dans le cas où plusieurs règles sont présentes, seule la procédure de création change avec deux boucles de lecture successives permettant d'effectuer le remplacement de deux caractères non-terminaux différents. Ces deux boucles ayant la même forme, on ne présentera pas ce cas. Mais le code donné en annexe \ref{codepythonfonct2} en donne une illustration compréhensible.
|
||
|
|
|
||
|
|
\subsection{Programmation}
|
||
|
|
|
||
|
|
\subsubsection{Approche non récursive}
|
||
|
|
Comme toujours dans le domaine de la programmation, il y a pour chaque problèmes beaucoup de solutions possibles. Même si l'objectif de ce cours n'est pas la programmation, deux solutions différentes vont être présentées, non récursive et récursive, répondant toutes les deux à la description algorithmique présentée au point \ref{algo}. En effet, dans le cadre d'un cours sur les langages, il est une fois de plus intéressant de montrer la diversité des approches, sans pour autant se focaliser particulièrement sur les avantages des différents modes de programmation. Par contre, on abordera pas ces problèmes en programmation orientée objet ou à travers d'autres languages tels que java par exemple. Mais il est évidemment envisageable de le faire par la suite.
|
||
|
|
|
||
|
|
Dans la section \ref{algo}, on a vu la décomposition du problème de génération des L-system en deux procédures d'une part de production des motifs à partir de la grammaire et d'autre part d'interprétation de ceux-ci par turtle. Le code complet est donné en annexe \ref{codepythonfonct}. On ne va détailler ici que les aspects non liés au langage de programmation utilisé. Cependant, il faut signaler qu'on a utilisé un découpage du problème en \emph{fonction} pour des raisons de clarté uniquement et qu'on a aussi mélangé variables \emph{globale} et \emph{locales}, \emph{procédures} et \emph{fonctions} pour mettre en jeu ces notions dans un programme fonctionnel. Mais, on ne les définira pas ici.
|
||
|
|
|
||
|
|
\paragraph{La création de la chaine} consiste essentiellement en une boucle qui parcourt successivement tous les carctères.
|
||
|
|
\begin{lstlisting}[language=Python]
|
||
|
|
while j < len(axiom):
|
||
|
|
pointeur1 = axiom[j]
|
||
|
|
\end{lstlisting}
|
||
|
|
La lecture se fait en plaçant le caractère j de l'axiome dans une variable \verb|pointeur1| qui permettra de décider du caractère terminal ou non d'un caractère. En effet, par remplacement de la règle dans les symboles non terminaux de l'axiome, la boucle va créer un nouvel axiome, nommé \verb|axiome2|, qui sera utilisé comme axiome de départ à chaque itération. Ainsi, on a :
|
||
|
|
\begin{lstlisting}[language=Python]
|
||
|
|
# Symboles non terminaux
|
||
|
|
if pointeur1 == 'F':
|
||
|
|
# remplacement de la regle dans l'axiome
|
||
|
|
axiom2 = axiom2 + regle
|
||
|
|
\end{lstlisting}
|
||
|
|
On voit qu'on remplace le caractère \verb|F| par la chaine correspondante de la règle. Par contre, la lecture d'un sybole terminal ne donne lieu à aucun remplacement. On réécrit simmplement ce symbole tel quel.
|
||
|
|
|
||
|
|
Ainsi, au fur et à mesure de la lecture des caractères,on construit par concaténation une nouvelle chaìne \verb|axiom2| qui sera à la base de la prochaine itération.
|
||
|
|
|
||
|
|
\paragraph{L'interprétation de la chaine} se fait à nouveau par lecture de celle-ci. Après création, elle est passée à la procédure d'interprétation via le paramètre \verb|axiom|, la chaine de caractère qui sera lue. Ensuite, pour les symboles de déplacement et d'orientation, l'interprétation est simple :
|
||
|
|
\begin{lstlisting}[language=Python]
|
||
|
|
# Interpreation
|
||
|
|
if pointeur2 == 'F':
|
||
|
|
forward(longueur)
|
||
|
|
elif pointeur2 == '+':
|
||
|
|
left(angle)
|
||
|
|
elif pointeur2 == '-':
|
||
|
|
right(angle)
|
||
|
|
\end{lstlisting}
|
||
|
|
Par contre, pour les symboles de mémorisation, la procédure est quelque peu plus complexe :
|
||
|
|
\begin{lstlisting}[language=Python]
|
||
|
|
elif pointeur2 == '[':
|
||
|
|
# memorisation de la position courante
|
||
|
|
laposition.append(position())
|
||
|
|
langle.append(heading())
|
||
|
|
elif pointeur2 == ']':
|
||
|
|
# retour a la derniere position et suppression de celle-ci
|
||
|
|
up()
|
||
|
|
goto(laposition[len(laposition)-1][0],\
|
||
|
|
laposition[len(laposition)-1][1])
|
||
|
|
del laposition[len(laposition)-1]
|
||
|
|
setheading(langle[len(langle)-1])
|
||
|
|
del langle[len(langle)-1]
|
||
|
|
down()
|
||
|
|
\end{lstlisting}
|
||
|
|
Tout d'abord, on utilise ici un tableau, nommé \verb|laposition| pour mémoriser chaque couple abscisse et ordonnée de la tortue et un autre tableau, nommé \verb|langle| pour mémoriser sa direction.
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Puis, pour le retour à la position mémorisée, on réalise un \verb|goto| aux coordonnées mémorisées et un \verb|setheading| pour revenir à la direction enregistrée. Enfin, il ne faut pas oublier de supprimer des deux tableaux la position à laquelle on est revenu. Cela se fait par deux \verb|del|. Notez que pendant le retour il ne faut pas que la tortue soit en position d'écriture. On lève donc le crayon avant le retour et on le baisse après.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
En fin de compte, grâce à l'utilisation de fonctions (et procédures), on peut écrire le programme principal avec une grande clarté :
|
||
|
|
\begin{lstlisting}[language=Python]
|
||
|
|
initialisation()
|
||
|
|
gram = grammaire()
|
||
|
|
## gram[0] retourne l'angle
|
||
|
|
## gram[1] retourne l'axiome
|
||
|
|
## gram[2] retourne la regle
|
||
|
|
|
||
|
|
axio = production(gram[1], gram[2])
|
||
|
|
interpretation(gram[0], axio)
|
||
|
|
\end{lstlisting}
|
||
|
|
L'initialisation se fait par le placement de la tortue et la mémorisation des paramètre, axiome et règle. Puis, vient naturellement la production et l'interprétation.
|
||
|
|
|
||
|
|
\subsubsection{Approche récursive}
|
||
|
|
Une autre approche de la génération de L-system fait usage d'une technique de programmation particulièrement intéressante : la récursivité. Il s'agit de l'appel d'une fonction à elle-même. Pour les L-system, il s'agit donc de ne plus générer la chaine de caractère, mais de lire l'axiome en renvoyant simultanément à la fonction appelée, à chaque occurence d'un caractère non terminal. Il n'est alors pas évident de suivre ce que fait le programme. C'est pourquoi on va maintenant reprendre une forme légérement différente de celle donnée précédemment du flocon de Koch pour l'étudier dans le détail. Le code complet est donne en annexe \ref{codepythonfloconrecursif}. Seule la partie purement récursive est présentée ci-dessous :
|
||
|
|
\begin{lstlisting}[language=Python]
|
||
|
|
def production(nbiteration, longueur, angle, axiome, regle):
|
||
|
|
if nbiteration == 0 :
|
||
|
|
forward(longueur)
|
||
|
|
else:
|
||
|
|
i = 0
|
||
|
|
while i < len(regle):
|
||
|
|
regle1 = regle[i]
|
||
|
|
if regle1 == 'F':
|
||
|
|
production(nbiteration-1, longueur/3,\
|
||
|
|
angle, axiome, regle)
|
||
|
|
if regle1 == '+':
|
||
|
|
left(angle)
|
||
|
|
if regle1 == '-':
|
||
|
|
right(angle)
|
||
|
|
i = i + 1
|
||
|
|
\end{lstlisting}
|
||
|
|
Et la figure \ref{Kochrecursif1} en donne l'interprétation graphique.
|
||
|
|
|
||
|
|
\begin{figure*}[t]
|
||
|
|
\centering
|
||
|
|
\includegraphics[width=5cm]{kochrecursif1.eps}
|
||
|
|
\caption{Flocon de Koch récursif.\label{Kochrecursif1}}
|
||
|
|
\end{figure*}
|
||
|
|
|
||
|
|
Le code est remarquable de concision, mais complexe à apréhender.
|
||
|
|
|
||
|
|
\smallskip
|
||
|
|
Le c\oe ur de la récursivité se trouve dans le test de reconnaissance du caractère \verb|F|. Il s'agit du caractère non terminal et il est nécessaire de le remplacer par l'ensemble des caractères de la règle. Mais, au lieu de réaliser simplement ce remplacement, on renvoie à la fonction de production. Cela n'a pas pour effet de remplacer le caractère non terminal par les symboles de la règle, mais de renvoyer sur une fonction, en l'occurence celle dans laquelle on se trouve, qui va le faire. Or, cette fonction va encore s'appeler elle-même à la lecture du caractère \verb|F| et ainsi de suite.
|
||
|
|
|
||
|
|
Le même processus va ainsi se répéter un nombre de fois déterminé par la variable \verb|nbiteration|. Comme à chaque appel de la fonction de production on diminue la variable contenant le nombre d'itération, quand celle-ci devient nulle, on stoppe l'apppel récursif et on trace un segment.
|
||
|
|
|
||
|
|
Ensuite, on retourne à la dernière procédure appelée pour réaliser l'instruction qui suit l'appel récursif selon la règle donnée, par exemple une instruction terminale de rotation. Et on continue pour réaliser une suite d'instructions terminales ou si non terminales, pour réaliser un appel récursif à la fonction principale.
|
||
|
|
|
||
|
|
Il est très difficile de réprésenter chaque étape de ce processus. Cependant, la figure \ref{appelrecursif} tente d'en donner une représentation graphique qui montre l'appel et le retour des processus dans l'ordre des flèches numérotées.
|
||
|
|
|
||
|
|
\begin{figure*}[t]
|
||
|
|
\centering
|
||
|
|
\begin{psfrags}
|
||
|
|
\psfrag{production(...)}{production(...)}
|
||
|
|
\psfrag{if regle1}{if regle1 == 'F':}
|
||
|
|
\psfrag{production}{production}
|
||
|
|
\psfrag{de}{(\scriptsize nbiteration-1,longueur-1)}
|
||
|
|
\psfrag{if regle2}{if regle1 == '+'}
|
||
|
|
\psfrag{left}{left(angle)}
|
||
|
|
\psfrag{if nbiteration}{if nbiteration == 0:}
|
||
|
|
\psfrag{forward}{forward(longueur)}
|
||
|
|
\psfrag{1}{1}
|
||
|
|
\psfrag{2}{2}
|
||
|
|
\psfrag{3}{3}
|
||
|
|
\psfrag{4}{4}
|
||
|
|
\psfrag{5}{5}
|
||
|
|
\psfrag{6}{6}
|
||
|
|
\includegraphics[width=12cm]{production.eps}
|
||
|
|
\end{psfrags}
|
||
|
|
\caption{Flocon de Koch récursif.\label{appelrecursif}}
|
||
|
|
\end{figure*}
|
||
|
|
|
||
|
|
On voit que toute un série de procédures sont progressivement lancées les unes dans les autres. Puis, arrivées à leur terme, le tracé des segment se fait et elles se terminent par un retour à la procédure qui les a lancées. Finalement, tout aussi progressivement, on termine chacunes des procédures imbriquées.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
On a déjà remarqué que le code est plus concis que celui issu d'une simple lecture-interprétation. Par contre, il est moins clair, demanderait donc pour la modification une relecture attentive qui peut prendre du temps et il faudrait se demander s'il est plus performant.
|
||
|
|
|
||
|
|
\medskip
|
||
|
|
Voilà. Comme le but de ce cours n'est pas la programmation récursive, nous finirons là cette analyse en précisant cependant les limites de celle-ci. En effet, avec la récursivité on utilise toujours la même règle. L'axiome n'est donc pas utilisé ou considéré égal à \verb|F|. Certes, on peut envisager des moyens de contourner ce problème en réalisant l'axiome hors de la procédure récursive, en utilisant une récursivité indirecte ou en remplaçant à un moment bien précis la règle par l'axiome. Mais cela complique le code et l'avantage en concision de la récursivité s'amenuise.
|
||
|
|
|
||
|
|
\section{Conclusion}
|
||
|
|
Nous avons parcouru avec cette introduction aux L-system beaucoup de notions d'informatiques importantes. Les langages, leur reconnaissance, les grammaires, l'algorithmique et finalement différents modes de programmation nous ont permis de comprendre le rôle essentiel joué par les structures formelles que l'informatique théorique met à notre disposition. Les limites de ce cours ne nous ont cependant pas permis d'aborder d'autres notions tout aussi importantes comme les résaux de Pétri ou les machines de Turing. Par contre, l'étude des L-system marque clairement la puissance de la modélisation informatique des structures biologiques. Plus, elle fait entrevoir une correspondance fascinante entre le développenent des organisme vivants et des constructions répétitives très structurées, finalement très bien décrites par le langage mathématique.
|
||
|
|
|
||
|
|
\Closesolutionfile{ans} % ferme le fichier Solutions.tex qui contient les solutions
|
||
|
|
\vfill
|
||
|
|
\pagebreak % met les solutions sur une autre page
|
||
|
|
\section{Solutions des exercices}
|
||
|
|
\Readsolutionfile{ans} % importe les données du fichier Solutions.tex
|
||
|
|
|
||
|
|
\myclearpage
|
||
|
|
|
||
|
|
%\appendix
|
||
|
|
|
||
|
|
\section{Annexes}
|
||
|
|
|
||
|
|
\subsection{Code python plante}\label{codepythonfonct}
|
||
|
|
|
||
|
|
\begin{lstlisting}[language=Python]
|
||
|
|
# -*- coding: utf-8 -*-
|
||
|
|
from turtle import *
|
||
|
|
|
||
|
|
# Generation de plante par grammaire L-system
|
||
|
|
|
||
|
|
def initialisation():
|
||
|
|
# Definition des variables independantes de la grammaire
|
||
|
|
global nbiteration, longueur
|
||
|
|
nbiteration = 5
|
||
|
|
longueur = 3
|
||
|
|
|
||
|
|
def grammaire():
|
||
|
|
# Definition de la grammaire
|
||
|
|
angle = 25.7
|
||
|
|
axiom = 'F'
|
||
|
|
|
||
|
|
regle = 'FF-[-F+F+F]+[+F-F-F]'
|
||
|
|
#regle = 'F[+F]F[-F][F]'
|
||
|
|
#regle = 'F[+F]F[-F]F'
|
||
|
|
#regle = 'F+FF-FF-F-F+F+FF-F-F+F+FF+FF-F'
|
||
|
|
|
||
|
|
return angle, axiom, regle
|
||
|
|
|
||
|
|
def production(axiom, regle):
|
||
|
|
# Generation de la chaine de caracteres
|
||
|
|
i = 0
|
||
|
|
while i < nbiteration:
|
||
|
|
j = 0
|
||
|
|
axiom2 = ''
|
||
|
|
while j < len(axiom):
|
||
|
|
pointeur1 = axiom[j]
|
||
|
|
|
||
|
|
# Symboles non terminaux
|
||
|
|
if pointeur1 == 'F':
|
||
|
|
# remplacement de la regle dans l'axiome
|
||
|
|
axiom2 = axiom2 + regle
|
||
|
|
|
||
|
|
# Symboles terminaux
|
||
|
|
if pointeur1 == '+':
|
||
|
|
axiom2 = axiom2 + '+'
|
||
|
|
if pointeur1 == '-':
|
||
|
|
axiom2 = axiom2 + '-'
|
||
|
|
if pointeur1 == '[':
|
||
|
|
axiom2 = axiom2 + '['
|
||
|
|
if pointeur1 == ']':
|
||
|
|
axiom2 = axiom2 + ']'
|
||
|
|
|
||
|
|
j = j + 1
|
||
|
|
axiom = axiom2
|
||
|
|
i = i + 1
|
||
|
|
print axiom
|
||
|
|
return axiom
|
||
|
|
|
||
|
|
def interpretation(angle, axiom):
|
||
|
|
# Interpretation de la chaine par turtle
|
||
|
|
k = 0
|
||
|
|
laposition = []
|
||
|
|
langle = []
|
||
|
|
while k < len(axiom):
|
||
|
|
pointeur2 = axiom[k]
|
||
|
|
|
||
|
|
# Interpreation
|
||
|
|
if pointeur2 == 'F':
|
||
|
|
forward(longueur)
|
||
|
|
elif pointeur2 == '+':
|
||
|
|
left(angle)
|
||
|
|
elif pointeur2 == '-':
|
||
|
|
right(angle)
|
||
|
|
elif pointeur2 == '[':
|
||
|
|
# memorisation de la position courante
|
||
|
|
laposition.append(position())
|
||
|
|
langle.append(heading())
|
||
|
|
elif pointeur2 == ']':
|
||
|
|
# retour a la derniere position et suppression de celle-ci
|
||
|
|
up()
|
||
|
|
goto(laposition[len(laposition)-1][0], laposition[len(laposition)-1][1])
|
||
|
|
del laposition[len(laposition)-1]
|
||
|
|
setheading(langle[len(langle)-1])
|
||
|
|
del langle[len(langle)-1]
|
||
|
|
down()
|
||
|
|
|
||
|
|
k = k + 1
|
||
|
|
|
||
|
|
# Placement initial de la tortue
|
||
|
|
up()
|
||
|
|
backward(495)
|
||
|
|
down()
|
||
|
|
|
||
|
|
# Programme principal
|
||
|
|
## gram[0] retourne l'angle
|
||
|
|
## gram[1] retourne l'axiome
|
||
|
|
## gram[2] retourne la regle
|
||
|
|
|
||
|
|
initialisation()
|
||
|
|
gram = grammaire()
|
||
|
|
|
||
|
|
axio = production(gram[1], gram[2])
|
||
|
|
interpretation(gram[0], axio)
|
||
|
|
|
||
|
|
#quit()
|
||
|
|
\end{lstlisting}
|
||
|
|
|
||
|
|
\subsection{Code python plante à deux règles}\label{codepythonfonct2}
|
||
|
|
|
||
|
|
\begin{lstlisting}[language=Python]
|
||
|
|
# -*- coding: utf-8 -*-
|
||
|
|
from turtle import *
|
||
|
|
|
||
|
|
# Generation de plante par grammaire L-system
|
||
|
|
|
||
|
|
def initialisation():
|
||
|
|
# Definition des variables independantes de la grammaire
|
||
|
|
global nbiteration, longueur
|
||
|
|
# Pour le flocon de Koch
|
||
|
|
#nbiteration = 3
|
||
|
|
#longueur = 2
|
||
|
|
|
||
|
|
# Pour le flocon de Koch Island
|
||
|
|
#nbiteration = 3
|
||
|
|
#longueur = 2
|
||
|
|
|
||
|
|
# Pour la plante
|
||
|
|
#nbiteration = 5
|
||
|
|
#longueur = 5
|
||
|
|
|
||
|
|
# Pour la plante 2
|
||
|
|
#nbiteration = 5
|
||
|
|
#longueur = 5
|
||
|
|
|
||
|
|
# Pour la plante 3
|
||
|
|
#nbiteration = 4
|
||
|
|
#longueur = 8
|
||
|
|
|
||
|
|
# Pour la plante 4
|
||
|
|
#nbiteration = 7
|
||
|
|
#longueur = 1
|
||
|
|
|
||
|
|
# Pour la plante 5
|
||
|
|
#nbiteration = 7
|
||
|
|
#longueur = 1
|
||
|
|
|
||
|
|
# Pour la plante 6
|
||
|
|
nbiteration = 5
|
||
|
|
longueur = 4
|
||
|
|
|
||
|
|
def grammaire():
|
||
|
|
# Definition de la grammaire
|
||
|
|
# Pour le flocon de Koch
|
||
|
|
#angle = 90
|
||
|
|
#axiom = 'F-F-F-F'
|
||
|
|
#regle = 'F+F-F-F+F'
|
||
|
|
|
||
|
|
# Pour le flocon de Koch Island
|
||
|
|
#angle = 90
|
||
|
|
#axiom = 'F-F-F-F'
|
||
|
|
#regle = 'F-F+F+FF-F-F+F'
|
||
|
|
|
||
|
|
# Pour la plante
|
||
|
|
#angle = 25.7
|
||
|
|
#axiom = 'F'
|
||
|
|
#regle = 'F[+F]F[-F]F'
|
||
|
|
|
||
|
|
# Pour la plante 2
|
||
|
|
#angle = 20
|
||
|
|
#axiom = 'F'
|
||
|
|
#regle = 'F[+F]F[-F][F]'
|
||
|
|
|
||
|
|
# Pour la plante 3
|
||
|
|
#angle = 22.5
|
||
|
|
#axiom = 'F'
|
||
|
|
#regle = 'FF-[-F+F+F]+[+F-F-F]'
|
||
|
|
|
||
|
|
# Pour la plante 4
|
||
|
|
#angle = 20
|
||
|
|
#axiom = 'X'
|
||
|
|
#regle1 = 'F[+X]F[-X]+X'
|
||
|
|
#regle2 = 'FF'
|
||
|
|
|
||
|
|
# Pour la plante 5
|
||
|
|
angle = 25.7
|
||
|
|
axiom = 'X'
|
||
|
|
regle1 = 'F[+X][-X]FX'
|
||
|
|
regle2 = 'FF'
|
||
|
|
|
||
|
|
# Pour la plante 6
|
||
|
|
angle = 22.5
|
||
|
|
axiom = 'X'
|
||
|
|
regle1 = 'F-[[X]+X]+F[+FX]-X'
|
||
|
|
regle2 = 'FF'
|
||
|
|
|
||
|
|
return angle, axiom, regle1, regle2
|
||
|
|
|
||
|
|
def production(axiom, regle1, regle2):
|
||
|
|
# Generation de la chaine de caracteres
|
||
|
|
i = 0
|
||
|
|
while i < nbiteration:
|
||
|
|
j = 0
|
||
|
|
axiom2 = ''
|
||
|
|
while j < len(axiom):
|
||
|
|
pointeur1 = axiom[j]
|
||
|
|
|
||
|
|
# Symboles non terminaux
|
||
|
|
if pointeur1 == 'X':
|
||
|
|
# remplacement de la regle dans l'axiome
|
||
|
|
axiom2 = axiom2 + regle1
|
||
|
|
|
||
|
|
# Symboles terminaux
|
||
|
|
if pointeur1 == '+':
|
||
|
|
axiom2 = axiom2 + '+'
|
||
|
|
if pointeur1 == '-':
|
||
|
|
axiom2 = axiom2 + '-'
|
||
|
|
if pointeur1 == '[':
|
||
|
|
axiom2 = axiom2 + '['
|
||
|
|
if pointeur1 == ']':
|
||
|
|
axiom2 = axiom2 + ']'
|
||
|
|
if pointeur1 == 'F':
|
||
|
|
axiom2 = axiom2 + 'F'
|
||
|
|
|
||
|
|
j = j + 1
|
||
|
|
axiom = axiom2
|
||
|
|
print axiom
|
||
|
|
|
||
|
|
m = 0
|
||
|
|
axiom3 = ''
|
||
|
|
while m < len(axiom):
|
||
|
|
pointeur2 = axiom[m]
|
||
|
|
|
||
|
|
# Symboles non terminaux
|
||
|
|
if pointeur2 == 'F':
|
||
|
|
# remplacement de la regle dans l'axiome
|
||
|
|
axiom3 = axiom3 + regle2
|
||
|
|
|
||
|
|
# Symboles terminaux
|
||
|
|
if pointeur2 == '+':
|
||
|
|
axiom3 = axiom3 + '+'
|
||
|
|
if pointeur2 == '-':
|
||
|
|
axiom3 = axiom3 + '-'
|
||
|
|
if pointeur2 == '[':
|
||
|
|
axiom3 = axiom3 + '['
|
||
|
|
if pointeur2 == ']':
|
||
|
|
axiom3 = axiom3 + ']'
|
||
|
|
if pointeur2 == 'X':
|
||
|
|
axiom3 = axiom3 + 'X'
|
||
|
|
|
||
|
|
m = m + 1
|
||
|
|
axiom = axiom3
|
||
|
|
i = i + 1
|
||
|
|
|
||
|
|
print axiom
|
||
|
|
return axiom
|
||
|
|
|
||
|
|
def interpretation(angle, axiom):
|
||
|
|
# Interpretation de la chaine par turtle
|
||
|
|
k = 0
|
||
|
|
laposition = []
|
||
|
|
langle = []
|
||
|
|
while k < len(axiom):
|
||
|
|
pointeur2 = axiom[k]
|
||
|
|
|
||
|
|
# Interpreation
|
||
|
|
if pointeur2 == 'F':
|
||
|
|
forward(longueur)
|
||
|
|
elif pointeur2 == '+':
|
||
|
|
left(angle)
|
||
|
|
elif pointeur2 == '-':
|
||
|
|
right(angle)
|
||
|
|
elif pointeur2 == '[':
|
||
|
|
# memorisation de la position courante
|
||
|
|
laposition.append(position())
|
||
|
|
langle.append(heading())
|
||
|
|
elif pointeur2 == ']':
|
||
|
|
# retour a la derniere position et suppression de celle-ci
|
||
|
|
up()
|
||
|
|
goto(laposition[len(laposition)-1][0], laposition[len(laposition)-1][1])
|
||
|
|
del laposition[len(laposition)-1]
|
||
|
|
setheading(langle[len(langle)-1])
|
||
|
|
del langle[len(langle)-1]
|
||
|
|
down()
|
||
|
|
|
||
|
|
k = k + 1
|
||
|
|
|
||
|
|
# Placement initial de la tortue
|
||
|
|
up()
|
||
|
|
backward(400)
|
||
|
|
down()
|
||
|
|
|
||
|
|
# Programme principal
|
||
|
|
## gram[0] retourne l'angle
|
||
|
|
## gram[1] retourne l'axiome
|
||
|
|
## gram[2] retourne la regle
|
||
|
|
|
||
|
|
initialisation()
|
||
|
|
gram = grammaire()
|
||
|
|
axio = production(gram[1], gram[2], gram[3])
|
||
|
|
interpretation(gram[0], axio)
|
||
|
|
|
||
|
|
#quit()
|
||
|
|
|
||
|
|
\end{lstlisting}
|
||
|
|
|
||
|
|
\subsection{Code python flocon de Koch récursif}\label{codepythonfloconrecursif}
|
||
|
|
|
||
|
|
\begin{lstlisting}[language=Python]
|
||
|
|
# -*- coding: utf-8 -*-
|
||
|
|
from turtle import *
|
||
|
|
|
||
|
|
# Generation de plante par grammaire L-system
|
||
|
|
|
||
|
|
def initialisation():
|
||
|
|
# Definition des variables independantes de la grammaire
|
||
|
|
# Pour le flocon de Koch
|
||
|
|
nbiteration = 3
|
||
|
|
longueur = 200
|
||
|
|
angle = 45
|
||
|
|
axiome = 'F'
|
||
|
|
regle = 'F+F--F+F'
|
||
|
|
return nbiteration, longueur, angle, axiome, regle
|
||
|
|
|
||
|
|
def production(nbiteration, longueur, angle, axiome, regle):
|
||
|
|
if nbiteration == 0 :
|
||
|
|
forward(longueur)
|
||
|
|
else:
|
||
|
|
i = 0
|
||
|
|
while i < len(regle):
|
||
|
|
regle1 = regle[i]
|
||
|
|
if regle1 == 'F':
|
||
|
|
production(nbiteration-1, longueur/3,\
|
||
|
|
angle, axiome, regle)
|
||
|
|
if regle1 == '+':
|
||
|
|
left(angle)
|
||
|
|
if regle1 == '-':
|
||
|
|
right(angle)
|
||
|
|
i = i + 1
|
||
|
|
|
||
|
|
# Placement initial de la tortue
|
||
|
|
up()
|
||
|
|
backward(200)
|
||
|
|
down()
|
||
|
|
|
||
|
|
# Programme principal
|
||
|
|
## init[1] : nbiteration
|
||
|
|
## init[2] : longueur
|
||
|
|
## init[3] : angle
|
||
|
|
## init[4] : axiome
|
||
|
|
## init[5] : regle
|
||
|
|
|
||
|
|
init = initialisation()
|
||
|
|
production(init[0], init[1], init[2], init[3], init[4])
|
||
|
|
right(120)
|
||
|
|
production(init[0], init[1], init[2], init[3], init[4])
|
||
|
|
right(120)
|
||
|
|
production(init[0], init[1], init[2], init[3], init[4])
|
||
|
|
\end{lstlisting}
|
||
|
|
|
||
|
|
\myclearpage
|
||
|
|
|
||
|
|
%\theendnotes
|
||
|
|
|
||
|
|
\myclearpage
|
||
|
|
|
||
|
|
%\renewcommand{\bibname}{Bibliographie} % pour mettre autre chose que bibliographie, par défaut avec babel
|
||
|
|
\nocite{CJ06,PP94,PP94,TO07,GP09,BD11} % pour mettre toutes les entrées dans la biblio, y compris celles non citées ds le texte
|
||
|
|
\bibliographystyle{apalike-fr} % le style de bibliographie apalike francisé
|
||
|
|
%\bibliographystyle{apalike} % le style de bibliographie
|
||
|
|
\bibliography{../../Bibliographies/BiblioCours} % définit le fichier des réf. biblio. nom.bib
|
||
|
|
|
||
|
|
% le logiciel utilisé pour faire la biblio est kbibtex
|
||
|
|
%\printindex{} % attention, pour que l'index soit mis à jour il faut lancer la commande de konsole : makeindex -s ../Perso.ist nom_du_cours.idx
|
||
|
|
% le Perso.ist est un fichier disant qu'il faut mettre des lettres entre les parties de l'index
|
||
|
|
|
||
|
|
%\renewcommand{\listfigurename}{Liste des figures}
|
||
|
|
%\listoffigures % ai tout basculé après la table des matières car je n'arrivais pas à éliminer le petit bug ci-dessous. Mais le compagnon latex fait idem.
|
||
|
|
%\listoftables % un petit problème (bug ?) d'alignement m'a fait retirer provisoirement cette liste
|
||
|
|
|
||
|
|
\end{document}
|
||
|
|
\endinput % termine l'importation des solutions
|