%oral
%% CCINP 24, ex A, corrigé, à débugguer
%% Grammaires pour des langages de programmation
%% Grammaires, Langages
%% 
%% *


\noindent On considère l'alphabet $\Sigma_0=\e{a,b,c,\cd z}$ des lettres minuscules, et une grammaire ayant comme symbole initial $S$ et les règles $S\ra AS|A$ et $A\ra\sigma $ avec $\sigma\in\Sigma_0$. 

\msk

\Qu Sans démonstration, quel est le langage engendré par cette grammaire?

\begin{correction}
  C'est $\Sigma_0^+$.
\end{correction}

\noindent On étudie un langage de programmation fictif, et on cherche à représenter les identificateurs (i.e. les noms de variables) valides dans ce langage. Un identificateur est valide lorsqu’il contient des caractères de $\Sigma_1=\e{a,b,c,\cd z,A,B,\cd Z, 0,1,\cd,9,\_}$ et qu’il ne commence pas par un chiffre.

\msk

\Qu Donner une grammaire qui engendre les identificateurs de notre langage.

\begin{correction}
  (On s'autorise à utiliser des majuscules pour désigne les non terminaux.)
  
  $S \lora P N$

  $P \lora a|\cd|Z|\_$

  $N \lora aN|\cd|zN|AN|\cd|ZN|0N|\cd|9N|\_N|\ep$
\end{correction}

\msk


\noindent On note $E$ le symbole initial d’une grammaire engendrant les
expressions booléennes du langage et on définit un non-terminal $I$ engendrant les programmes
du langage
avec les règles:

\msk

\noindent $(1).\ I\ra E;$\\
$(2).\ I\ra ;$\\
$(3).\ I\ra while(E)I$\\
$(4).\ I\ra B$\\

\noindent $B$ est un non-terminal permettant de représenter des blocs,
c’est-à-dire une liste (potentiellement vide) de programmes délimitée
par une accolade ouvrante et une accolade fermante. L’exemple suivant
est un bloc:

\verb|{a!=4; {while(b) 3+5=t;; 5=2; {}} d=5-a;}|

\msk
\Qu Montrer que les mots engendrés par $I$
  finissent soit par un point-virgule, soit par une accolade fermante.

  \begin{correction}
    Soit $u$ dans le langage engendré à partir de $I$. On considère la feuille la plus à droite d'un arbre de dérivation de $u$. Celle-ci contient un symbole terminal qui est le symbole le plus à droite d'une règle de production: ce peut donc être un point-virgule (règles (1) ou (2)) ou une accolade fermante (règles permettant d'engendrer les blocs).

    On peut également raisonner par récurrence sur le nombre de
    dérivation ou par induction sur les arbres de dérivation, mais ça
    n'est pas indispensable.
  \end{correction}
  
  \msk
\Qu Ajouter aux règles (1) à (4) une ou des règles permettant de décrire les blocs engendrés par $B$.

  \begin{correction}
    $S\ra \ep|IS$\\
    $B\ra \e{S}$
  \end{correction}
  
  \msk
\Qu On note $L_A$ l'ensemble des expressions arithmétiques de notre langage. Par exemple, \li{2+a}, \li{(aB5-16)*4} ou encore \li{(4-(16*B))/4} sont dans $L_A$. Montrer que $L_A$ n'est pas régulier.

  \begin{correction}
    $L_A=\cap (^*)^*=\e{(^n)^n,\ n\inN}$, qui est au notations près le langage $\e{a^nb^n,\ n\inN}$. On montre que ce langage n'est pas régulier comme dans le cours.

    Par contraposée de la stabilité par intersection des langages
    réguliers, $L_A$ n'est donc pas régulier.
  \end{correction}
  
