Corrigé CCINP 2025 Informatique MPI — Partie I (Q1 à Q5) : Grammaire non contextuelle : ambiguïté, récursivité gauche, langage

Sujet officiel du concours CCINP, session 2025, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

La grammaire $G$ a pour terminaux $a, b, c$ , pour symbole initial $S$ , et pour règles

$S A B \to \to \to S a S ∣ A A b A ∣ B B c B ∣ ε$

On pose $u = ab c$ .

Q1. Donner une dérivation à gauche de $u$ ; qu'en conclure sur $u$ ?
Q2. Donner deux arbres de dérivation de $aa$ ; en déduire que $G$ est ambiguë.

Une grammaire est récursive gauche directe si elle a une règle $X \to X α$ ; $X$ est alors une variable récursive gauche.
Q3. Quelles sont les variables récursives gauches de $G$ ?

Algorithme d'élimination : une règle $X \to X α ∣ β$ ( $β$ ne commençant pas par $X$ ) est remplacée par $X \to β X^{'}$ et $X^{'} \to α X^{'} ∣ ε$ , avec $X^{'}$ une variable nouvelle.
Q4. Construire la grammaire $G^{'}$ , non récursive gauche directe, équivalente à $G$ .
Q5. Prouver que le langage de $G^{'}$ (ou de $G$ ) est ${a, b, c}^{*}$ .

Corrigé

On note $\Rightarrow$ la dérivation immédiate, $\Rightarrow^{*}$ sa clôture, et $L_{X}$ l'ensemble des mots de terminaux dérivables depuis la variable $X$ ; le langage de la grammaire est $L_{S}$ .

Q1. On remplace à chaque pas la variable la plus à gauche (soulignée) :

$S \Rightarrow S a S \Rightarrow A a S \Rightarrow B a S \Rightarrow a S \Rightarrow a A \Rightarrow a A b A \Rightarrow a B b A \Rightarrow ab A \Rightarrow ab B \Rightarrow ab B c B \Rightarrow ab c B \Rightarrow ab c .$

Les règles employées sont, dans l'ordre, $S \to S a S$ , $S \to A$ , $A \to B$ , $B \to ε$ , $S \to A$ , $A \to A b A$ , $A \to B$ , $B \to ε$ , $A \to B$ , $B \to B c B$ , $B \to ε$ , $B \to ε$ . On a $S \Rightarrow^{*} u$ : le mot $u = ab c$ appartient au langage engendré par $G$ . Ce que le correcteur attend : une suite de mots où c'est toujours la variable la plus à gauche qui est remplacée, et non un arbre (le jury relève la confusion).

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →