QCM : Langages formels et automates — 11 questions

Explication

Le langage engendré rassemble tous les mots entièrement terminaux obtenus en appliquant successivement des règles depuis l’axiome. Les mots qui contiennent encore un non-terminal correspondent à des étapes intermédiaires de dérivation.

Explication

Dans une grammaire régulière, chaque règle produit un mot terminal ou un mot terminal suivi d’au plus un non-terminal. La possibilité d’utiliser des formes générales avec plusieurs non-terminaux correspond à une grammaire hors-contexte générale, et non à cette restriction régulière.

Explication

Un langage est un sous-ensemble de $V_t^\star$, où $V_t^\star$ rassemble tous les mots construits sur le vocabulaire. Une suite finie particulière est un mot, tandis qu’un langage peut regrouper plusieurs mots.

Explication

Un mot est une suite finie de symboles du vocabulaire, et le cas de longueur nulle correspond au mot vide $\varepsilon$. Un sous-ensemble de l’ensemble des mots constitue plutôt un langage, et non un mot individuel.

Explication

Un mot est une suite finie d’éléments de V_t, avec le mot vide ε pour la suite de longueur nulle. La définition ne concerne pas les suites infinies ou celles hors de V_t.

Explication

$u^0$ représente le mot vide ε, qui est la puissance zéro d’un mot. La réponse 1 est incorrecte car elle désigne le mot initial, pas la puissance.

Explication

Les AFD ont pour rôle principal de reconnaître si un mot appartient à un langage en suivant un chemin unique déterminé par la fonction de transition. Contrairement aux AFN, ils ne peuvent pas générer tous les mots, mais uniquement reconnaître ceux qui leur sont acceptés.

Explication

L'AFD possède une transition unique pour chaque symbole dans chaque état, ce qui le rend déterministe, alors que l'AFN peut avoir plusieurs transitions ou aucune, ce qui le rend non déterministe. La déterminisation permet de transformer un AFN en un AFD sans changer le langage reconnu.

Explication

La coïncidence indique que tout langage régulier peut être reconnu par un automate, dérivé d’une grammaire régulière, et exprimé par une expression régulière. La réponse incorrecte suppose une hiérarchie qui n’existe pas, car tous ces concepts sont équivalents pour les langages réguliers.

Explication

La déterminisation consiste à construire un AFD à partir d’un AFN en utilisant des états qui sont des ensembles d’états de l’AFN, ce qui permet de reconnaître le même langage de façon déterministe et plus efficace. La suppression des transitions non déterministes est une étape de cette procédure, mais la méthode principale consiste à créer des états de parties.

Explication

Le lemme de pompage affirme que si un langage est reconnaissable, alors tout mot suffisamment long peut être décomposé en trois parties, dont une partie v non vide peut être répétée indéfiniment. Cela permet de prouver qu’un langage n’est pas reconnaissable en trouvant un mot qui viole cette propriété.