Aspects Algébriques

Grammaires Algébriques

1.

Pour chaque langage, construire une grammaire algébrique qui l'engendre :

(a): ${\cal L}=a^\star b$
(b): ${\cal L}=a^nb^n$
(c): ${\cal L}=a^nb^p\vert n>p\}$
(d): ${\cal L}=\{a^nb^m\vert n\not=m\}$
(e): ${\cal L}=\{a^nb^mc^pd^q\vert n=p\,\vee\,m=q\}$
(f): ${\cal L}=\{a^nb^mc^p\vert n+p\leq m\}$
(g): ${\cal L}=\{a^nb^m\vert n\not=m+2\}$
(h): ${\cal L}=\{uc\overline{u}\vert u\in(a\vert b)^\star\}$
(i): ${\cal L}=\{u\overline{u}\vert u\in(a\vert b)^\star\}$
(j): ${\cal L}=\{u\in(a\vert b)^\star\vert u=\overline{u}\}$
(k): ${\cal L}=\{uc\overline{v}\vert u,v\in(a\vert b)^\star\,\wedge\,u\not=v \,\wedge\,\vert u\vert=\vert v\vert\}$
(l): ${\cal L}=\{a^nb^m\vert\leq n\leq m\}$
(m): ${\cal L}=\{a^nb^\star c^nd^\star\vert n\geq 0\}\cup \{a^\star b^nc^\star d^n\vert n\geq 0\}$
(n): ${\cal L}=\{a^nb^nb^\star b^qc^q\vert n,q\geq 0\}$
(o): ${\cal L}=\{\mbox{ensemble des expressions rationnelles sur $\{a,b\}$ }\}$

2.