QCM - Théorème de Kleene

QCM - Théorème de Kleene

Question 1. Le théorème de Kleene établit que :

Tout langage est régulierUn langage est régulier si et seulement s'il est reconnaissable par un automate finiLes automates finis reconnaissent tous les langagesLes expressions régulières ne peuvent pas décrire tous les langages réguliers

Question 2. L'algorithme de Berry-Sethi permet de :

Minimiser un automateConstruire un automate à partir d'une expression régulièreConvertir un automate en expression régulièreDéterminiser un automate

Question 3. Une expression régulière est linéaire si :

Elle ne contient pas d'étoileChaque lettre y apparaît au plus une foisElle décrit un langage finiElle ne contient pas d'union

Question 4. Pour une expression régulière $e$, $P(L(e))$ représente :

Les dernières lettres possibles des mots de $L(e)$Les premières lettres possibles des mots de $L(e)$Les facteurs de longueur 2L'ensemble des puissances de $L(e)$

Question 5. Un langage $L$ est local si un mot $u \neq \varepsilon$ appartient à $L$ ssi :

$u$ a une longueur paireLa première lettre est dans $P(L)$, la dernière dans $S(L)$, et tous les facteurs de longueur 2 sont dans $F(L)$$u$ est un palindrome$u$ ne contient pas de répétition

Question 6. L'automate de Glushkov pour une expression régulière à $k$ lettres (avec multiplicité) a :

$k$ états$k + 1$ états$2k$ états$k^2$ états

Question 7. Pour montrer qu'un langage régulier est reconnaissable, on utilise :

Le lemme de pompageL'algorithme de Berry-Sethi ou ThompsonLa minimisationLa déterminisation

Question 8. Pour montrer qu'un langage reconnaissable est régulier, on peut utiliser :

L'algorithme d'Arden ou l'élimination d'étatsLe lemme de pompageLa déterminisationL'algorithme de Dijkstra

Question 9. Un automate est local si :

Il est minimalToutes les transitions étiquetées par une même lettre arrivent au même étatIl n'a qu'un seul état finalIl est déterministe

Question 10. Le lemme d'Arden permet de résoudre des équations de la forme :

$X = AX \cup B$ où $A$ et $B$ sont des langages, avec $\varepsilon \notin A$$X = X^2$$X + Y = Z$$X = \emptyset$