QCM : Théorie des langages rationnels — 65 questions

Explication

Un langage associe une signification à des suites d’objets élémentaires. Un alphabet, en revanche, est un ensemble de symboles et ne constitue pas en lui-même un ensemble de suites interprétées.

Explication

Un alphabet est un ensemble fini de symboles, appelés lettres. Un langage peut être fini ou infini et contient des mots construits à partir de l’alphabet.

Explication

Le symbole $\varepsilon$ désigne le mot vide, c’est-à-dire la suite finie ne contenant aucune lettre. Il ne représente pas un alphabet ni une lettre ajoutée aux mots.

Explication

Par définition, $\Sigma^*$ regroupe tous les mots sur $\Sigma$, y compris $\varepsilon$, alors que $\Sigma^+$ en retire le mot vide. La différence porte donc sur l’inclusion de $\varepsilon$, non sur la nature des lettres.

Explication

La longueur compte toutes les lettres du mot, y compris les répétitions, et le mot vide a une longueur nulle. Le nombre d’occurrences d’une lettre particulière constitue une mesure différente, notée par exemple $|w|_a$.

Explication

La concaténation conserve d’abord toutes les lettres de $w_1$, puis ajoute celles de $w_2$, ce qui donne $ab01$. Le mot $01ab$ correspondrait à la concaténation dans l’ordre inverse.

Explication

La concaténation réunit les lettres des deux mots, donc sa longueur est la somme de leurs longueurs. Cette opération possède aussi $\varepsilon$ comme élément neutre, mais cela ne change pas la règle additive.

Explication

La concaténation est associative : le regroupement des facteurs ne modifie pas le mot final, mais elle n’est pas commutative : inverser deux mots peut changer leur ordre. Ainsi, l’ordre des facteurs compte même si le parenthésage ne compte pas.

Explication

Une distance est une fonction à valeurs réelles positives qui vérifie la séparation, la symétrie et l’inégalité triangulaire. Les autres propriétés proposées concernent d’autres structures ou opérations et ne définissent pas une distance.

Explication

L’égalité $d(x,y)=d(y,x)$ exprime la symétrie de la distance, car les deux arguments peuvent être échangés. La séparation est exprimée par $d(x,y)=0\Longleftrightarrow x=y$.

Explication

La distance d’édition considérée ici est le nombre minimal d’insertions et de suppressions de lettres permettant de transformer un mot en un autre. Elle ne repose donc pas sur les substitutions ni sur la simple comparaison des lettres différentes.

Explication

Un langage est décidable lorsqu’un algorithme termine sur toute entrée et donne la bonne réponse d’appartenance. La reconnaissance avec une exécution potentiellement infinie ne suffit pas pour établir la décidabilité.

Explication

Le problème de savoir si un programme s’arrête sur une entrée donnée est indécidable, indépendamment du langage de programmation. Les trois autres langages disposent d’algorithmes de décision simples ou connus.

Explication

L’union regroupe les mots appartenant à au moins un des deux langages, y compris ceux qui appartiennent aux deux. L’appartenance simultanée aux deux langages caractérise plutôt l’intersection.

Explication

Le complémentaire est défini par $A^{\complement}=\Sigma^*\setminus A$ : il contient tous les mots de l’univers qui ne sont pas dans $A$. Une différence entre deux langages conserve au contraire des mots du premier langage.

Explication

Les lois de De Morgan donnent $(A \cup B)^{\complement}=A^{\complement}\cap B^{\complement}$. Un mot est absent de l’union lorsqu’il est absent de chacun des deux langages.

Explication

La concaténation est $L_1\cdot L_2=\{w_1\cdot w_2\mid w_1\in L_1\text{ et }w_2\in L_2\}$ : chaque mot commence par un élément de $L_1$ et se termine par un élément de $L_2$. Les autres descriptions correspondent respectivement à l’union, l’intersection et la différence.

Explication

Une expression régulière décrit un langage grâce à l’alternation, à la concaténation et à l’étoile de Kleene. L’alternation offre un choix entre motifs, tandis que la concaténation les enchaîne.

Explication

L’opérateur optionnel vérifie $e?=e+\varepsilon$ et autorise donc l’absence ou une occurrence de $e$. L’expression $e^+=ee^*$ correspond plutôt à au moins une occurrence.

Explication

La syntaxe commence par les atomes $\emptyset$, $\varepsilon$ et les lettres de l’alphabet, puis construit $e_1+e_2$, $e_1e_2$ et $e_1^*$ à partir d’expressions existantes. Les opérations d’intersection et de complémentaire ne font pas partie des constructeurs inductifs indiqués.

Explication

L’expression régulière $e$ est la description syntaxique, tandis que sa sémantique $L(e)$ est le langage associé. Confondre ces deux objets revient à traiter l’expression comme l’ensemble des mots qu’elle désigne.

Explication

Par définition, $L(\varepsilon)=\{\varepsilon\}$ : un seul mot est présent, le mot vide. Le langage vide correspond à l’expression $\varnothing$, ce qui constitue la confusion classique entre ces deux expressions.

Explication

L’opérateur $+$ représente l’union, donc $L(e_1+e_2)=L(e_1)\cup L(e_2)$. La concaténation des langages correspond à l’expression $e_1e_2$, tandis que l’étoile s’applique à une seule expression.

Explication

Un langage est rationnel s’il est décrit par une expression régulière, c’est-à-dire s’il existe $e\in\mathrm{Reg}_\Sigma$ tel que $L=L(e)$. La finitude ou le fait de contenir tous les mots ne constitue pas la définition générale de cette classe.

Explication

L’opérateur d’union permet de construire directement une expression régulière pour l’union de deux langages rationnels. L’intersection et le complément ne sont pas fournis directement par cette définition syntaxique, même si d’autres résultats peuvent ensuite établir leur clôture.

Explication

Les langages rationnels sont tous décidables, donc un langage indécidable comme $H$ ne peut pas appartenir à cette classe. La rationalité n’implique ni la finitude ni l’égalité avec l’ensemble de tous les mots.

Explication

Dans cette définition, $I$ est l’ensemble non vide des états initiaux et $F$ l’ensemble des états acceptants. Les inverser confond le point de départ des chemins avec leur condition d’acceptation.

Explication

L’acceptation exige l’existence d’un chemin portant exactement le mot $w$, partant d’un état initial et aboutissant à un état acceptant. La présence d’une lettre ou d’un chemin partiel ne suffit pas à établir l’acceptation.

Explication

Par définition, $L(A)=\{w\in\Sigma^*\mid A\text{ accepte }w\}$ rassemble les mots acceptés par l’automate. Les mots refusés sont dans le complément relatif à $\Sigma^*$, pas dans $L(A)$.

Explication

Le refus peut provenir de deux situations : un chemin étiqueté par le mot existe mais ne termine pas dans un état acceptant, ou bien aucun chemin ne porte ce mot. La multiplicité des chemins n’entraîne pas en elle-même le refus, car un seul chemin acceptant suffit.

Explication

Un DFA possède exactement un état initial et, pour chaque état et chaque lettre, au plus une arête sortante portant cette lettre. La présence de plusieurs chemins pour une même lettre correspondrait à une situation non déterministe.

Explication

Dans un NFA, l’existence d’au moins un chemin acceptant suffit pour accepter le mot. Exiger que tous les chemins soient acceptants confond le fonctionnement d’un NFA avec une condition plus restrictive qui n’est pas celle donnée ici.

Explication

Un automate complet dispose, depuis chaque état, d’au moins une arête sortante étiquetée par chaque lettre de l’alphabet. La condition « au plus une transition » décrit le déterminisme, pas la complétude.

Explication

Une transition spontanée est étiquetée par $\varepsilon$ et peut être empruntée sans consommer de lettre de l’entrée. L’état puits et la redirection des transitions manquantes relèvent de la complétion, pas des transitions spontanées.

Explication

La complétion ajoute un état puits non acceptant, muni d’une boucle pour chaque lettre, puis y dirige les transitions manquantes. Cette construction rend l’automate complet tout en préservant son langage.

Explication

Le théorème de Kleene affirme que toute expression régulière peut être reconnue par un ε-NFA ayant le même langage. Il ne garantit pas directement que l’automate obtenu soit déterministe, complet ou dépourvu de transitions epsilon.

Explication

L’algorithme de Thompson construit inductivement un ε-NFA avec un unique état initial et un unique état acceptant distinct. Les transitions epsilon font partie de cette construction, et l’algorithme ne réalise pas directement une déterminisation.

Explication

La fermeture epsilon avant regroupe les états accessibles depuis q en utilisant uniquement des transitions epsilon et contient également q lui-même. La notion qui remonte vers q correspond à une fermeture arrière, tandis que la lecture d’une lettre n’intervient pas ici.

Explication

La fermeture epsilon avant contient les états atteignables depuis q en ne suivant que des transitions epsilon. Remonter vers q correspond à une fermeture arrière, qui est une notion différente.

Explication

L’initialisation place q ainsi que ses successeurs immédiats par transition epsilon dans la cellule correspondante. Les itérations ajoutent ensuite les fermetures déjà calculées afin de prendre en compte les chemins epsilon plus longs.

Explication

Toute transition étiquetée partant d’un état p atteint depuis q par des transitions epsilon doit être reproduite depuis q avec la même lettre et la même destination. Cette règle permet de conserver les chemins acceptés après retrait des transitions epsilon.

Explication

Si p peut atteindre un état acceptant r uniquement par des transitions epsilon, p doit devenir acceptant dans l’automate transformé. Cette déclaration préserve l’acceptation des mots qui se terminent avant ces transitions epsilon.

Explication

Un état est accessible lorsqu’un chemin le relie à un état initial. La possibilité d’atteindre un état final depuis lui décrit plutôt la co-accessibilité.

Explication

La co-accessibilité signifie qu’un chemin partant de l’état mène à un état final. L’accessibilité, elle, s’évalue dans le sens allant des états initiaux vers l’état considéré.

Explication

L’élagage conserve l’intersection des états accessibles et co-accessibles, obtenue par ces deux recherches successives. La recherche des co-accessibles part des états finaux après inversion des arêtes, et non des états initiaux.

Explication

Les états inutiles ne contribuent à aucun calcul allant d’un état initial à un état final, donc leur suppression conserve le langage reconnu. Cette opération ne détermine pas à elle seule le caractère déterministe ou complet de l’automate.

Explication

La construction par sous-ensembles étiquette chaque état du DFA par un ensemble d’états du NFA. Cet ensemble regroupe les configurations possibles après la lecture d’un préfixe, plutôt qu’un état unique.

Explication

Le successeur est $S_a=\{q\mid\exists p\in S,\ p\xrightarrow{a}_A q\}$, c’est-à-dire l’union des destinations obtenues depuis les états de $S$. Il suffit donc qu’un état de l’ensemble possède la transition pertinente.

Explication

Un ensemble d’états du DFA est acceptant dès qu’il contient au moins un état acceptant du NFA. Une seule configuration acceptante suffit, car le NFA accepte lorsqu’une exécution possible aboutit à un état final.

Explication

Chaque état du DFA est un sous-ensemble d’états du NFA, et un ensemble de $n$ éléments possède $2^n$ sous-ensembles. Cette borne inclut les ensembles possibles, même si certains ne sont pas atteignables dans la construction.

Explication

Un DFA traite chaque symbole du mot puis s’arrête, ce qui fournit un algorithme de décision pour l’appartenance au langage. La décidabilité porte sur l’existence d’une procédure terminante, tandis que la rationalité porte sur la reconnaissance par automate fini.

Explication

La longueur du parcours dépasse le nombre d’états, donc le principe des tiroirs force la répétition d’un état. Le segment situé entre les deux visites fournit un facteur non vide $y$ dans $w=x\cdot y\cdot z$, répétable dans le parcours.

Explication

Le lemme affirme que tout mot de $L$ de longueur au moins $n_0$ s’écrit $w=x\cdot y\cdot z$ avec $y\ne\varepsilon$ et $x\cdot y^*\cdot z\subseteq L$. Il ne concerne donc pas une égalité de longueurs entre les facteurs ni tous les mots possibles.

Explication

On peut décider l’appartenance en vérifiant la forme du mot et l’égalité entre les nombres de $a$ et de $b$, mais aucun automate fini ne reconnaît ce langage. La non-rationalité n’implique donc pas l’indécidabilité.

Explication

La preuve distingue les trois emplacements possibles du facteur pompé : dans le bloc des $a$, dans le bloc des $b$ ou à cheval sur les deux. Les autres démarches concernent respectivement les restes modulo trois, les parités ou la minimisation d’un automate.

Explication

Un langage rationnel est reconnaissable avec une quantité constante de mémoire, tandis que $L$ exige de comparer deux quantités pouvant croître sans borne. Les parités et les restes modulo trois, eux, peuvent être stockés dans un nombre fini d’états.

Explication

La procédure incrémente le compteur pendant le bloc des $a$, le décrémente pendant le bloc des $b$ et accepte si l’entrée est entièrement lue avec un compteur nul. Les autres procédures suivent des critères de parité ou de divisibilité qui ne comparent pas les deux blocs.

Explication

Chaque lettre possède deux possibilités de parité, donc les deux parités combinées donnent quatre configurations mémorisables. Trois états suffisent pour un reste modulo trois, mais pas pour ces deux informations binaires indépendantes.

Explication

Deux états sont indistinguables si, pour tout mot $w\in\Sigma^*$, l’acceptation de $w$ depuis l’un équivaut à son acceptation depuis l’autre. Le nombre de transitions, la longueur des préfixes ou la position graphique ne déterminent pas cette propriété.

Explication

La minimisation forme les classes d’équivalence des états indistinguables, puis fusionne les membres de chaque classe. Les états non acceptants peuvent être nécessaires et les états distinguables ne peuvent pas être fusionnés sans modifier le langage.

Explication

Le théorème de Myhill-Nerode établit l’existence et l’unicité de l’automate déterministe minimal, avec autant d’états que de classes d’indistinguabilité. Le nombre d’états ne dépend pas du nombre de mots acceptés et l’expression rationnelle n’est pas unique.

Explication

La partition initiale distingue l’acceptation de $\varepsilon$, puis les transitions sont examinées pour détecter des successeurs situés dans des classes différentes. Le processus répète ces divisions jusqu’à ce qu’aucune nouvelle séparation ne soit nécessaire.

Explication

Il y a conflit lorsque, pour une même lettre, les deux états conduisent à des successeurs appartenant à des classes différentes. Des successeurs dans une même classe ne justifient pas une séparation, même s’ils sont des états distincts.

Explication

La partition stabilisée définit les états du nouvel automate : la classe de l’état initial est initiale et toute classe contenant un état acceptant est acceptante. Les états ne sont donc pas conservés individuellement lorsque plusieurs appartiennent à une même classe.

Explication

Les automates déterministes, non déterministes et à transitions $\varepsilon$ reconnaissent exactement les langages décrits par des expressions rationnelles appropriées. Les différences de modèle n’élargissent pas la famille des langages rationnels.