Base d'épreuves orales scientifiques de concours aux grandes écoles

Échangeons, communiquons ...

Epreuve Orale 217

Informations de classement de l'épreuve

Année : 2011 ou avant

Filière : MP

Concours : ENS (non PSI)

Matière(s) concernée(s) : Informatique

Type(s) de sujet(s) : Exercice

Mots-clés relatifs au contenu de l'épreuve : Automates finis - Langages

Détails sur l'épreuve Sources

Énoncé(s) donné(s)
Soit L un langage. On note $\frac{1}{2}L=\left\{u\:\big/\:\exists v,\: (uv)\in L \quad\text{et}\quad |u|=\frac{1}{2}|uv|\right\}$

Question 1 : Un exemple, déterminer $\frac{1}{2}L$ pour $L=(a(aba+bab))^{*}$.

Question 2 : Montrer que, si L est régulier, $\frac{1}{2}L$ est régulier.
Quid de la réciproque ?

Question 3 : On note, pour  $r\in\mathbb{N}^{*}, \frac{1}{r}L=\left\{u\:\big/\:\exists v,\: (uv)\in L\quad\text{et}\quad|u|=\frac{1}{r}|uv|\right\}$
Montrer que si L est régulier, alors $\frac{1}{r}L$ est régulier.

Question 4 : Soient $p$ et $q$ deux entiers premiers entre eux. On note $\frac{p}{q}L=\left\{u\:\big/\:\exists v, \: (uv)\in L\quad\text{et}\quad|u|=\frac{p}{q}|uv|\right\}$.
Montrer que si $L$ est régulier, alors $\frac{p}{q}L$ est régulier.

Commentaires

Aucun commentaire posté pour le moment