Grammaire Hors Contexte

PythonTechOutils Mathématique pour InformatiqueLeave a comment

\chapter{Grammaire hors contexte} \section{Notion de Grammaire} \begin{definition} On appelle grammaire alg\'{e}brique ou grammaire hors contexte la donn\'{e}e d'un 4-uple $G=(V,\Sigma ,P,S)$ o\`{u} :\newline $-$ $\Sigma $ est un ensemble fini appel\'{e} alphabet dont les \'{e}l\'{e}% ments sont appel\'{e}s des symbols terminaux\newline $-$ $V$ est un autre alphabet disjoint de $\Sigma $\ dont les \'{e}l\'{e}% ments sont appel\'{e}s des varibles ou des symbols non terminaux\newline $-$ $S$ est un \'{e}l\'{e}ment de $V$ appel\'{e} symbol initial.\newline $-$ $P$ un sous ensemble fini de $V\times (\Sigma \cup V)^{\ast }$ appel\'{e} ensemble des r\`{e}gles de d\'{e}rivation ou de production de $G.$ \end{definition} \begin{notation} Les \'{e}l\'{e}ment de $V$ sont not\'{e}s par des lettres majuscules $A,B...$ Tandis que les \'{e}l\'{e}ment de $\Sigma $ seront not\'{e}s par des miniscules $a,b...$ \end{notation} \begin{notation} Une r\`{e}gle $(A,w)\in P$ est not\'{e}e par $A\rightarrow w.$ Un ensemble de r\`{e}gles form\'{e}es \`{a} partir d'une seule variable $A$ : $% A\rightarrow w_{1},A\rightarrow w_{2},...,A\rightarrow w_{n}$ sera not\'{e} $% A\rightarrow w_{1}|w_{2}|...|w_{n}.$ \end{notation}

\section{Langage g\'{e}n\'{e}r\'{e} par une grammaire} Soit $G=(V,\Sigma ,P,S)$ une grammaire alg\'{e}brique \begin{remark} En partant du symbol initial et en executant un nombre fini de r\`{e}gles de $P$ on obtient un langage qu'on note $L(G)$ appel\'{e} langage g\'{e}n\'{e}r% \'{e} par la grammaire $G.$ \end{remark} \begin{example} $G=(V,\Sigma ,P,S)$ $V=\{S\}$ $,$ $\Sigma =\{a,b\}$ et $P=\{(S,aSb),(S,% \varepsilon )\}$ ( $P$ peut \^{e}tre sh\'{e}matis\'{e} par $S\rightarrow aSb$ \ et \ $S\rightarrow \varepsilon )$ \end{example} Pour v\'{e}rfifier par exemple que le mot $ab\in L(G)$ on ex\'{e}cute successivement les deux r\`{e}gles $\underline{S}\rightarrow a\underline{S}% b\rightarrow a\underline{\varepsilon }b=ab$ dans chaque \'{e}tape nous avons soulign\'{e} une lettre pour indiquer la lettre qui va \^{e}tre remplac\'{e}% e dans l'\'{e}tape suivante). De la m\^{e}me mani\`{e}re on verifie que le mot $a^{2}b^{2}\in L(G):$ $\underline{S}\rightarrow a\underline{S}% b\rightarrow aa\underline{S}bb\rightarrow aa\underline{\varepsilon }% bb=a^{2}b^{2}$ et ainsi de suite par recurrence on obtient $% L(G)=\{a^{n}b^{n}/n\in %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \}$ \begin{definition} Une grammaire hors contexte est dite r\'{e}guli\`{e}re \`{a} droite si toutes ces r\`{e}gles sont de l'un des types suivants : $A\rightarrow a$ \ , $A\rightarrow aB$ \ , $A\rightarrow \varepsilon $ avec $A,B$ des variable de $V$ \ et $a\in \Sigma .$ Elle est dite r\'{e}guli\`{e}re \`{a} gauche si toutes ses r\`{e}gles sont de l'un des types suivants : $A\rightarrow a$ \ , $A\rightarrow Ba$ \ , $A\rightarrow \varepsilon .$ \end{definition} \begin{example} $G=(V,\Sigma ,P,S)$ $V=\{S\}$ $,$ $\Sigma =\{a,b\}$ et $\ P$ : $S\rightarrow aS$ $|$ $\varepsilon $ \ $G$ \ est une grammaire r\'{e}guli\`{e}re \`{a} gauche. \end{example} \begin{theorem} Un langage $L$ est rationnel (r\'{e}gulier) si et seulement s'il existe une grammaire r\'{e}guli\`{e}re $G$ ( \`{a} droit ou \`{a} gauche) telle que $% L=L(G).$ \end{theorem}

 

Younes Derfoufi
CRMEF OUJDA

Post Views: 5 554
Acheter sur Très Facile !

Leave a Reply