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 : 
Langages, Automates finis
Détails sur l'épreuve
É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.
Qualité de ce compte-rendu
0
Pas encore de note. Tout membre peut choisir une étoile...