Alphabets, Mots et Langages

PythonTechOutils Mathématique pour InformatiqueLeave a comment

1 - Notions d'alphabets, mots & langages

\chapter{Langages et automates} \section{Alphabets, Mots et Langages} \section{Notion pr\'{e}liminaires} \subsection{D\'{e}finitions et notations} \begin{definition} Un alphabet est un ensemble fini quelconque non vide. Les \'{e}l\'{e}ments d'un alphabet sont appel\'{e}s des \textbf{lettres }ou\textbf{\ Symbols}. \end{definition} \begin{notation} Un alphabet sera not\'{e} en g\'{e}n\'{e}ral par la lettre grec $\ \sum $ \end{notation} \begin{definition} Un mot est une suite finie de lettres \end{definition} \begin{example} $\sum =\{a,b,c,\ldots ,z\}$ est un alphabet , $a,b,c,$ \ldots\ sont des lettres, \textbf{math,cpr, oujda},\ldots\ sont des mots \end{example} \begin{notation} L'ensemble des mots sur $\sum $ \ sera not\'{e} $\sum^{\ast }$ \end{notation} \begin{example} $\sum =\{0,1,2,...\}=% %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion $ \ est un alphabet , $484,275,107,...$ \ sont des mots \end{example} \begin{notation} Le mot qui ne contient aucune lettre est appel\'{e} le mot vide not\'{e} $% \Lambda $ \end{notation} \begin{remark} On s'interesse seulement \`{a} la forme d'un mot qui peut \^{e}tre qq et on omet le sens du mot exemple : avhbrtys, jorbqhegd,... sont des mots. \end{remark} \begin{definition} La longueur d'un mot $x$ not\'{e} $|x|$ est le nombre de symbols qui le compose exemple si $x=arbre$ alors $|x|=5$ \end{definition} \begin{notation} Soit $x$ un mot de $\sum^{\ast }$ et $\sigma $ une lettre de $\sum $ le nombre d'apparition de \ $\sigma $\ dans $x$\ est not\'{e} $|x|_{\sigma }$ \end{notation} \begin{example} $|arbre|_{r}=2,$ \ $|arbre|_{a}=1$ ,\ $|abbcb|_{b}=3$ \end{example}

 

2 - Fonction de Parikh

\subsection{Fonction de Parikh} Soit $\sum $ un alphabet fini et ordonn\'{e}, et peut donc \^{e}tre consid% \'{e}r\'{e} comme un n-uplet $\sum =(\sigma _{1},\sigma _{2},...,\sigma _{n}) $ l'application $\psi :\sum^{\ast }\rightarrow

 

3 - Notion de langage

\section{Notion de langage} \begin{definition} Un langage est un ensemble de mots ( c.a.d un sous ensemble de $\sum^{\ast }$ $)$ \end{definition} \begin{definition} $\{$ $CPR,Oujda,Hay,AlMassira$ $\}$ est un langage\newline \end{definition} \begin{example} langage infini g\'{e}n\'{e}r\'{e} par un alphabet fini\newline L'ensemble des mots sur l'alphabet \ $\{a,b\}$ ne contenant pas la lettre \ $% b$ \ : $\{\Lambda ,a,aa,aaa,...\}$ est un exemple de langage infini qui est g% \'{e}n\'{e}r\'{e} par un alphabet fini \end{example}

4 - Opérations sur les langages

\section{Op\'{e}rations sur les mots et les langages} \subsection{Concatenation des mots} \begin{definition} La concatenation de deux mots \ $x$ \ et \ $y$ \ est le mot not\'{e} \ $% x\otimes y$ \ d\'{e}finit par : \newline $x\otimes y=xy$ \ c.a.d \ si \ $x=x_{1}x_{2}...x_{r}$ \ et \ $% y=y_{1}y_{2}...y_{s}$ \ alors \ $x\otimes y=x=x_{1}x_{2}...x_{r}$\ $% y_{1}y_{2}...y_{s}$ \end{definition} \begin{example} Si $\ x=lang$ \ et \ $y=age$ \ alors $x\otimes y=langage$ \end{example} \subsection{Concatenation des langages} \begin{definition} Soient \ $E$ \ et \ $F$ \ deux langages de l'alphabet $\sum .$ La concatenation \ de \ $E$ \ et \ $F$ \ est le langage d\'{e}finit par : \newline $E\otimes F=\{x\otimes y/(x,y)\in E\times F\}$ \end{definition} \begin{example} $E=\{u,v\}$ , \ $F=\{uv,vu\}$ \ $E\otimes F=\{% \unit{u}\unit{u}v,uvu,vuv,vvu\} $ \end{example} $E\otimes F$ \ sera not\'{e} par la suite simplement par \ $EF$ \begin{definition} Un langage est dit ferm\'{e} pour la loi $"\otimes "$ \ s'il est stable pour la concatenation ( i.e $\forall x,y\in E$ \ on a : $x\otimes y\in E$ \end{definition} \begin{example} $\{x^{n}/n\in %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \}$ \ est un langage ferm\'{e} \end{example}
\begin{definition} Soit \ $E$ \ un langage, le plus petit langage ferm\'{e} pour la concatenation contenant $E$ \ et \ $\{\Lambda \}$ est appel\'{e} la fermeture de $E$ \ et est not\'{e} \ $E^{\ast }$ \end{definition} \begin{remark} $E^{\ast }=\underset{k\geq 0}{\cup E^{k}}$ \end{remark} \begin{definition} $E^{\ast }=\underset{k\geq 0}{\cup E^{k}}$ \ est appel\'{e} \'{e}toile de Kleene ou fermeture de Kleenne du langage $E$ \end{definition} \begin{example} Soit \ $E$ \ un langage et \ $\ x$ \ un mot de $E$ \ alors on a:\newline $1)$ $\ \{x\}^{\ast }=\{x^{n}/n\in %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \}$\newline $2)$ \ $\{xx\}^{\ast }=\{x^{2n}/n\in %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \}$\newline $3)$ \ $\{xx,xxx\}^{\ast }=\{x^{n}/n\geq 2\}\cup \{\Lambda \}$\newline $4)$ \ $\{0,1\}^{\ast }$ \ est l'ensemble de tous les nombres entiers naturels ne contenant que les chiffres $0$ \ ou \ $1$\newline $5)$ \ $\varnothing ^{\ast }=\{\Lambda \}$ \end{example} \begin{notation} Si \ $x=x_{1}x_{2}...x_{r}$ \ on pose alors \ $\widetilde{x}% =x_{r}x_{r-1}...x_{1}$ \ appel\'{e} l'image miroir de $x$. Si \ $E$ \ est un langage on pose : $\widetilde{E}=\{\widetilde{x}/x\in E\}$ \ appel\'{e} l'image miroir de \ $E$ \end{notation} \begin{definition} Un mot \ $x$ \ verifiant : $\widetilde{x}=x$ \ est appel\'{e} palindrome \end{definition} \begin{example} laval, \ radar \ sont des palindromes \end{example}

5 - Langages réguliers

\section{Langage r\'{e}gulier} On dit qu'un langage L sur un alphabet $\Sigma $ \ est \textbf{r\'{e}gulier} ou \textbf{rationnel} si L peut \^{e}tre obtenu r\'{e}cursivement par :% \newline $\ 1)$ \ \`{a} partir des seuls langages de bases :\newline $-$ langage $\emptyset $\newline $-$ langage $\{\wedge \}$ \ ( langage form\'{e} uniquement par le symbol $% vide)$\newline $-$ langage de la forme $\{a\}$ avec $a\in \Sigma $\newline $2)$ \`{a} l'aide des seules op\'{e}rations :\newline $-$ r\'{e}uinion \newline $-$ Concat\'{e}ntion\newline $-$ \'{e}toile de Kleenne

6 - Langage résiduel

Langage résiduel <definition/>Soit L un langage sur l'alphabet Σ et u un mot de Σ^{∗}, on obtient un nouveau langage en posant u⁻¹L=L/u={v∈Σ^{∗}/uv∈L}. L/u est appelé le résiduel du langage L par rapport à u <example/>L={uuv,uw,vv,uu} alors L/u={uv,w,u} <theorem/>(Th de Myhill Nerode ) Un langage est reconnaissable si et seulement s'il n'a qu'un nombre fini de résiduels.

7 - Topologie sur un langage formel

Topologie sur un langage formel Distance sur un langage Pour tout langage L sur un alphabet Σ on définit une distance d:L×L→ℝ₊ (u,v)↦2^{|u∧v|} où u∧v est le plus long préfixe commun, de plus cette distance est ultramétrique d(u,w)≤max(d(u,v),d(v,w)) Topologie limite inductive sur la fermeture de Kleene X^{∗} On définit une topologie sur X^{(k)}=X.X...X (le langage sur l'alphabet X formé des mots de longueur k) en convenant qu'une partie O de X^{(k)} est ouverte si elle est une réunion quelconque d'ensemble de la forme : O₁.O₂...O_{k} ( Concaténation des O_{i} ) où O₁,...,O_{k} sont des ouverts de X. On munit ensuite la fermeture de Kleene X^{∗} de la topologie limite inductive à l'aide de la famille des injections canoniques i_{k}:X^{(k)}↪X^{∗}

X peut être considéré comme un sous espace topologique de X^{(k)} et par suite un sous espace topologique de X^{∗} à l'aide de l'injection continue i:X↪X^{(k)} x↦x.ϖ...ϖ où ϖ est le mot vide <remark/>Tout language L sur l'alphabet X est considéré comme un sous espace topologique de X^{∗} pour la topologie induite.

Younes Derfoufi
CRMEF OUJDA

Post Views: 3 113
Acheter sur Très Facile !

Leave a Reply