QCM - Automates finis

QCM - Automates finis

Question 1. Un automate fini non déterministe (AFN) est composé de :

$(\Sigma, Q, q_0, F, \delta)$ avec $\delta : Q \times \Sigma \to Q$$(\Sigma, Q, I, F, E)$ avec $E \subseteq Q \times \Sigma \times Q$Un ensemble de motsUne expression régulière

Question 2. Un automate est déterministe si :

Il a plusieurs états initiauxIl a un unique état initial et pour chaque état et lettre, au plus une transitionIl reconnaît un langage infiniIl a des $\varepsilon$-transitions

Question 3. Un mot est accepté par un automate si :

Il existe un chemin étiqueté par ce mot d'un état initial à un état finalIl passe par tous les étatsSa longueur est égale au nombre d'étatsIl ne contient que des lettres de l'alphabet

Question 4. Le langage reconnu par un automate $A$ est :

L'ensemble des états de $A$L'ensemble des mots acceptés par $A$L'alphabet de $A$L'ensemble des transitions de $A$

Question 5. Un automate est complet si :

Tous les états sont finauxPour chaque état et chaque lettre, il existe au moins une transitionIl n'a pas d'état initialIl reconnaît tous les mots

Question 6. Pour déterminiser un AFN à $n$ états, l'AFD résultant peut avoir au plus :

$n$ états$n^2$ états$2^n$ états$n!$ états

Question 7. L'algorithme de déterminisation utilise :

La construction par sous-ensembles (powerset construction)Un tri topologiqueLa programmation dynamiqueUn parcours en profondeur

Question 8. Le complémentaire d'un langage régulier est :

Pas toujours régulierToujours régulierToujours videToujours infini

Question 9. La complexité pour vérifier si un mot de longueur $m$ est accepté par un AFD à $n$ états est :

$O(n)$$O(m)$$O(nm)$$O(2^n)$

Question 10. Un automate minimal est :

Un automate qui ne reconnaît rienL'AFD avec le moins d'états reconnaissant un langage donnéUn automate sans état finalUn automate avec un seul état