QCM - Langages réguliers

QCM - Mots, langages et expressions régulières

Question 1. Un alphabet est :

Un ensemble fini de lettresUn ensemble nécessairement infini de lettresUne suite finie de motsUn langage contenant tous les mots possibles

Question 2. Laquelle de ces affirmations sur $\varepsilon$ est correcte ?

$\varepsilon$ est une lettre présente dans tout alphabet$\varepsilon$ est le langage vide$\varepsilon$ est le mot vide, de longueur $0$$\varepsilon$ est l'ensemble de tous les mots

Question 3. Que désigne $\Sigma^*$ ?

L'ensemble des mots non vides sur $\Sigma$L'ensemble de tous les mots sur $\Sigma$, y compris $\varepsilon$L'ensemble des mots de longueur $1$L'alphabet privé d'une lettre

Question 4. Un langage $L$ sur un alphabet $\Sigma$ est :

Une lettre de $\Sigma$Un unique mot de $\Sigma^*$Un sous-ensemble de $\Sigma^*$Toujours un ensemble fini

Question 5. Si $u=abc$ et $v=de$, que vaut la concaténation $uv$ ?

$deabc$$abcde$$\{abc,de\}$$abc+de$

Question 6. Quelle opération l'expression régulière $e_1|e_2$ représente-t-elle ?

L'union de $L(e_1)$ et $L(e_2)$L'intersection de $L(e_1)$ et $L(e_2)$La concaténation de $L(e_1)$ et $L(e_2)$Le complémentaire de $L(e_1)$

Question 7. Un langage est régulier si et seulement si :

Il est finiIl contient le mot videIl peut être décrit par une expression régulièreTous ses mots ont la même longueur

Question 8. On pose $\Sigma = \{a,b\}$. Lequel de ces mots appartient à $\Sigma^+$ mais pas à $\Sigma^2$ ?

$\varepsilon$$ab$$aba$$c$

Question 9. Pour $u=ab$ et $v=aba$, quelle affirmation décrit correctement $uv$ et $vu$ ?

$uv=vu$ car la concaténation est commutative$uv$ et $vu$ ont des longueurs différentes$uv=ababa$ et $vu=abaab$ : ils ont la même longueur mais sont distincts$uv$ n'est pas défini car $u$ et $v$ n'ont pas la même longueur

Question 10. Dans le mot $m=aabacb$, le mot $u=abc$ est :

Un facteur, mais pas un sous-motUn sous-mot, mais pas un facteurUn préfixe et un suffixeNi un facteur ni un sous-mot

Question 11. Soient $a,b\in\Sigma$ et $u\in\Sigma^*$. Si $au=ub$, que peut-on nécessairement conclure ?

$a=b$ et il existe $k\in\mathbb{N}$ tel que $u=a^k$$a\neq b$ et $u=\varepsilon$$u=ab$$u$ peut être n'importe quel mot

Question 12. Quelle stratégie permet de tester en temps linéaire si $u$ est un sous-mot de $m$ ?

Trier les lettres des deux mots puis comparer les résultatsÉnumérer tous les facteurs de $m$Parcourir $m$ une fois en avançant dans $u$ chaque fois que la lettre attendue est rencontréeTester uniquement si $u$ est un préfixe de $m$

Question 13. Soient $L_1=\{a,ab\}$ et $L_2=\{\varepsilon,b,bba\}$. Combien de mots distincts contient $L_1L_2$ ?

$3$$5$$6$$8$

Question 14. Quelles propriétés de la concaténation des langages sont vraies ? (plusieurs réponses possibles)

Elle est associativeElle est commutative$\{\varepsilon\}$ est son élément neutre$\emptyset$ est son élément absorbant

Question 15. Si $L=\{\varepsilon,a\}$, quel est le langage $L^2$ ?

$\{\varepsilon,a,aa\}$$\{\varepsilon,aa\}$$\{a,aa\}$$\{u^2\mid u\in L\}=\{\varepsilon,aa\}$

Question 16. Que valent $\emptyset^0$ et $\emptyset^*$ ?

Tous deux valent $\emptyset$$\emptyset^0=\{\varepsilon\}$ et $\emptyset^*=\{\varepsilon\}$$\emptyset^0=\emptyset$ et $\emptyset^*=\Sigma^*$$\emptyset^0=\{\varepsilon\}$ et $\emptyset^*=\emptyset$

Question 17. Pour $L=\{ab,b\}$, lequel de ces mots appartient à $L^*$ ?

$a$$abbab$$ba$$aba$

Question 18. Pour tout langage $L$, pourquoi a-t-on $(L^*)^*=L^*$ ?

Parce que $L^*$ est toujours finiParce que concaténer plusieurs concaténations de mots de $L$ revient encore à concaténer des mots de $L$Parce que l'étoile supprime le mot videSeulement parce que la concaténation est commutative

Question 19. Chaque singleton $\{a^n b^n\}$ est un langage régulier. Peut-on en déduire que $\bigcup_{n\in\mathbb{N}}\{a^n b^n\}$ est régulier ?

Oui, car toute union de langages réguliers est régulièreOui, car chaque mot de l'union est finiNon : la stabilité par union ne concerne ici que les unions finiesNon, car aucun langage fini n'est régulier

Question 20. Sur $\Sigma=\{a,b\}$, quelle expression décrit les mots ayant $ab$ comme facteur ?

$(a|b)^*ab(a|b)^*$$(a|b)^*a(a|b)^*b(a|b)^*$$ab^*$$(ab)^*$

Question 21. Sur $\Sigma=\{a,b\}$, quelle expression décrit les mots ayant $aba$ comme sous-mot ?

$(a|b)^*aba(a|b)^*$$(a|b)^*a(a|b)^*b(a|b)^*a(a|b)^*$$a^*b^*a^*$$(aba)^*$

Question 22. Quelle expression régulière décrit exactement les mots sur $\{a,b\}$ contenant au plus un $a$ ?

$b^*ab^*$$b^*(\varepsilon|a)b^*$$(a|b)^*$$a^*b^*$

Question 23. Quel ensemble de longueurs est décrit par $(a|b)((a|b)(a|b)(a|b))^*$ ?

Les longueurs multiples de $3$Les longueurs congrues à $1$ modulo $3$Les longueurs congrues à $2$ modulo $3$Toutes les longueurs strictement positives

Question 24. Quelle expression régulière décrit les mots sur $\{a,b\}$ contenant un nombre pair de $a$ ?

$b^*(ab^*ab^*)^*$$b^*ab^*$$(aa|b)^*$$a^*(ba^*ba^*)^*$

Question 25. Quelles équivalences d'expressions régulières sont correctes ? (plusieurs réponses possibles)

$e\emptyset\equiv\emptyset$$e\varepsilon\equiv e$$e|\emptyset\equiv e$$\emptyset^*\equiv\emptyset$

Question 26. Quelle expression régulière décrit le miroir du langage de $a(a|b)^*b$ ?

$a(a|b)^*b$$b(a|b)^*a$$b(b|a)a$$(a|b)^*ba$

Question 27. Pour démontrer par induction structurelle une propriété $P(e)$ de toutes les expressions régulières, quelles obligations faut-il vérifier ? (plusieurs réponses possibles)

$P(\emptyset)$, $P(\varepsilon)$ et $P(a)$ pour chaque lettre $a$La conservation de $P$ par union et concaténationLa conservation de $P$ par étoileLa conservation de $P$ par complémentaire