Alphabets, Mots et Langages

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

Leave a Reply

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
Best Wordpress Adblock Detecting Plugin | CHP Adblock