summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2018-03-14 15:24:35 +0100
committerDavid A. Madore <david+git@madore.org>2018-03-14 15:24:35 +0100
commit73db3637a6f734b9d8e4fcc83bd8d1b510920fed (patch)
tree65d1f5ec19aa97500b4346ab1785a3a8aac084be
parent53f7986147248bec53316fc9d1fa3d7d4b1eacd2 (diff)
downloadinf105-73db3637a6f734b9d8e4fcc83bd8d1b510920fed.tar.gz
inf105-73db3637a6f734b9d8e4fcc83bd8d1b510920fed.tar.bz2
inf105-73db3637a6f734b9d8e4fcc83bd8d1b510920fed.zip
Add an exercise on formal grammars.
-rw-r--r--controle-20180322.tex40
1 files changed, 40 insertions, 0 deletions
diff --git a/controle-20180322.tex b/controle-20180322.tex
index 516cd07..a1eb15e 100644
--- a/controle-20180322.tex
+++ b/controle-20180322.tex
@@ -140,6 +140,46 @@ résultant.
états, déterminer une expression rationnelle dénotant le langage $M$.
+%
+%
+%
+
+\exercice
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$. On appelle $L = L(G)$
+le langage défini par la hors-contexte $G$ d'axiome $S$ et de
+nonterminaux $N = \{S\}$ sur l'alphabet $\Sigma$ donnée par
+\[
+\begin{aligned}
+S &\rightarrow aSbS \;|\; aS \;|\; \varepsilon\\
+\end{aligned}
+\]
+
+(1) Donner deux arbres d'analyse (pour $G$) différents du mot $aab$.
+Que peut-on dire de la grammaire $G$ ?
+
+L'objet des questions suivantes (qui ne dépendent pas de la
+précédente) est de montrer que $L$ n'est pas rationnel.
+
+Soit $M$ le langage $\{a^i b^j : i,j\in\mathbb{N}\}$ constitué des
+mots de la forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels
+quelconques.
+
+(2) Donner une expression rationnelle qui dénote $M$.
+
+Soit $P$ le langage $\{a^i b^j : i\geq j\}$ constitué des mots de la
+forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels vérifiant $i\geq
+j$ (autrement dit, les mots de $M$ qui ont au moins autant de $a$ que
+de $b$).
+
+(3) Montrer que $P \subseteq L$.
+
+(4) Montrer que $L\cap M \subseteq P$.
+
+(5) Montrer que $P$ n'est pas rationnel.
+
+(6) Déduire des questions (2) à (5) que $L$ n'est pas rationnel.
+
%
%