QCM - Langages réguliers

QCM - Langages réguliers et mots

Question 1. Un alphabet est :

Un ensemble infini de lettresUn ensemble fini de lettresUne suite de motsUn langage

Question 2. Le mot vide est noté :

$\emptyset$$\varepsilon$$0$$\lambda$

Question 3. $\Sigma^*$ désigne :

L'alphabet sans le mot videL'ensemble de tous les mots sur $\Sigma$L'ensemble des lettres de $\Sigma$Le langage vide

Question 4. La concaténation de deux mots $u = abc$ et $v = de$ donne :

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

Question 5. Si $|u| = 3$ et $|v| = 4$, alors $|uv| =$ :

$7$$12$$3$$4$

Question 6. Un langage sur $\Sigma$ est :

Un alphabetUn sous-ensemble de $\Sigma^*$Un motUne lettre

Question 7. L'expression régulière $a^*b$ dénote :

L'ensemble des mots formés de $a$ suivis de $b$$\{b, ab, aab, aaab, \ldots\}$$\{ab\}$$\{a, b\}$

Question 8. L'opération $L_1 | L_2$ (ou $L_1 \cup L_2$) dénote :

L'intersection de $L_1$ et $L_2$L'union de $L_1$ et $L_2$La concaténation de $L_1$ et $L_2$Le complémentaire de $L_1$

Question 9. $u$ est un préfixe de $m$ si :

$m = uv$ pour un certain mot $v$$m = vu$ pour un certain mot $v$$u$ est une sous-suite de $m$$m$ contient $u$ comme facteur

Question 10. Un langage est régulier s'il peut être décrit par :

Une grammaire non-contextuelleUne expression régulièreUne équation différentielleUn algorithme polynomial

Question 11. Le lemme de l'étoile (pumping lemma) affirme que pour tout langage régulier $L$, il existe $N$ tel que :

Tout mot de $L$ a une longueur $\leq N$Tout mot $w \in L$ avec $|w| \geq N$ peut s'écrire $w = xyz$ avec $|xy| \leq N$, $|y| \geq 1$ et $\forall k, xy^kz \in L$$L$ contient exactement $N$ motsTout mot de longueur $N$ appartient à $L$

Question 12. Pour montrer que $L = \{a^n b^n \mid n \in \mathbb{N}\}$ n'est pas régulier, on utilise :

Le théorème de KleeneLe lemme de l'étoile (pumping lemma)L'algorithme de Berry-SethiLa déterminisation