Qu'est-ce qu'un langage en informatique formelle ?
Un ensemble de suites d’objets élémentaires avec une signification.
Qu'est-ce qu'un alphabet en théorie des langages ?
Un ensemble fini de symboles appelés lettres.
Qu'est-ce qu'un mot sur un alphabet Σ ?
Une suite finie, éventuellement vide, de lettres de Σ.
Comment est noté le mot vide ?
Par la lettre grecque ε.
Quelle est la différence entre Σ∗ et Σ+ ?
Σ∗ contient tous les mots, Σ+ tous les mots non vides.
Qu'est-ce qu'un langage L sur un alphabet Σ ?
Un ensemble de mots L inclus dans Σ∗.
Un langage peut-il être infini ?
Oui, un langage peut être fini ou infini.
Donnez un exemple de langage infini sur Σ = {0, 1}.
Les mots contenant un nombre pair de 1.
Qu'est-ce que la longueur d'un mot w ?
La longueur |w| est le nombre total de lettres de w.
Quelle est la longueur de w = 011101 ?
|w| = 6.
Combien de fois apparaît le symbole 1 dans w = 011101 ?
|w|1 = 4.
Qu'est-ce que la concaténation de deux mots w1 et w2 ?
C'est le mot obtenu en plaçant w2 après w1.
Quelle relation lie la longueur de w1 · w2 à celles de w1 et w2 ?
|w1 · w2| = |w1| + |w2|.
Quel est l'élément neutre de la concaténation ?
Le mot vide ε est l'élément neutre.
Pourquoi la concaténation n'est-elle pas commutative ?
Parce que w1 · w2 peut différer de w2 · w1.
Quand un mot w est-il un palindrome ?
Quand w est égal à son miroir wR.
Qu'est-ce qu'une distance sur un ensemble E ?
Une fonction d : E² → R+ vérifiant séparation, symétrie et inégalité triangulaire.
Quelle condition exprime la séparation pour une distance ?
Quelle condition exprime la symétrie pour une distance ?
Quelle inégalité doit vérifier une distance pour trois points ?
Qu'est-ce que la distance d'édition entre deux mots ?
Le nombre minimal d'insertions et suppressions pour transformer un mot en un autre.
Que mesure la distance d'édition entre deux mots ?
Le nombre minimal d'insertions et suppressions de lettres nécessaires.
Quelle est la distance d'édition entre "dog" et "bugs" ?
Elle vaut 5.
Comment obtenir la distance d'édition 5 entre "dog" et "bugs" ?
Par deux suppressions et trois insertions.
Qu'est-ce qu'un langage décidable sur un alphabet Σ ?
Un langage avec un algorithme répondant vrai pour tout mot dedans et faux pour tout mot hors.
Le langage des nombres premiers est-il décidable ?
Oui, il est décidable.
Quel algorithme permet de décider le langage des nombres premiers ?
Le crible d'Ératosthène.
Comment décide-t-on le langage vide ?
Par un algorithme qui répond toujours faux.
Comment décide-t-on le langage Σ∗ ?
Par un algorithme qui répond toujours vrai.
Le langage des programmes qui s'arrêtent sur une entrée donnée est-il décidable ?
Non, il est indécidable quel que soit le langage de programmation.
Comment décide-t-on le langage des programmes qui s'arrêtent en moins de dix secondes ?
En compilant et exécutant avec une limite de dix secondes.
Quand un mot w appartient-il à l'union A ∪ B de deux langages A et B ?
Si w appartient à A ou à B.
Qu'est-ce que le complémentaire A∁ d'un langage A ?
L'ensemble des mots de Σ∗ qui n'appartiennent pas à A.
Quelle égalité vérifie le complémentaire double A∁∁ ?
A∁∁ = A.
Que vaut l'union A ∪ A∁ pour un langage A ?
A ∪ A∁ = Σ∗.
Comment s'exprime la concaténation de deux langages L1 et L2 ?
L1 · L2 = {w1 · w2 | w1 ∈ L1 et w2 ∈ L2}.
Que représente Lk pour un langage L et un entier k ?
L'ensemble des mots obtenus en concaténant k mots de L, qui peuvent être différents.
Quelle est la définition de l'étoile de Kleene L∗ ?
L∗ = ⋃n≥0 Ln, ensemble des mots concaténant un nombre fini, éventuellement nul, de mots de L.
Qu'est-ce que Pref(L) pour un langage L ?
L'ensemble des mots qui sont des préfixes d'au moins un mot de L.
Qu'est-ce qu'une expression régulière ?
Un motif formel décrivant un langage par alternation, concaténation et étoile de Kleene.
Que représente e? dans une expression régulière ?
L'optionnel, soit e ou ε.
Que signifie e+ dans une expression régulière ?
Au moins une occurrence de e, soit ee∗.
Que représente en dans une expression régulière ?
Exactement n occurrences de e.
Quels sont les atomes de la syntaxe inductive de RegΣ ?
∅, ε et chaque lettre a ∈ Σ.
Quelles expressions forme-t-on avec e1 et e2 en RegΣ ?
Les expressions e1 + e2, e1e2 et e1∗.
Que fait la sémantique d'une expression régulière e ?
Elle associe à e un langage L(e) en interprétant ses atomes et opérateurs.
Qu'est-ce que la sémantique d'une expression régulière e ∈ RegΣ ?
C'est le langage L(e) défini inductivement selon la structure de e.
Quelle est la valeur de L(∅) en sémantique des expressions régulières ?
L(∅) est le langage vide ∅.
Que vaut L(ε) pour une expression régulière ?
L(ε) est le langage contenant uniquement la chaîne vide {ε}.
Que représente L(a) pour une lettre a ∈ Σ ?
L(a) est le langage contenant la lettre a {a}.
Comment s'exprime la concaténation L(e₁e₂) en termes de L(e₁) et L(e₂) ?
L(e₁e₂) est le produit L(e₁)·L(e₂).
Comment s'exprime l'union L(e₁+e₂) en termes de L(e₁) et L(e₂) ?
L(e₁+e₂) est l'union L(e₁) ∪ L(e₂).
Comment s'exprime l'étoile L(e₁^*) en termes de L(e₁) ?
L(e₁^*) est l'étoile de Kleene L(e₁)^*.
Qu'est-ce qu'un langage rationnel ?
Un langage L est rationnel s'il existe une expression régulière e telle que L=L(e).
Quelles opérations sur langages rationnels restent rationnelles ?
L'union, la concaténation et l'étoile conservent la rationalité.
Peut-on affirmer la clôture des langages rationnels par intersection et complément ?
Non, la définition syntaxique ne permet pas de l'affirmer directement.
Pourquoi tout langage fini est-il rationnel ?
Parce qu'il est décrit par une expression régulière de la forme w₁+…+wₙ.
Quels sont les langages rationnels parmi le vide et Σ* ?
Le langage vide ∅ et le langage Σ* sont tous deux rationnels.
Comment décrire Σ* si Σ={a₁,…,aₙ} ?
Par l'expression régulière (a₁+…+aₙ)*.
Un langage rationnel est-il toujours décidable ?
Oui, tout langage rationnel est décidable.
Qu'en est-il de la rationalité d'un langage indécidable comme H ?
Un langage indécidable comme H n'est pas rationnel.
Qu'est-ce qu'un automate fini ?
Un quintuplet A=(Q,Σ,δ,I,F) avec Q, Σ finis, δ⊆Q×Σ×Q, I≠∅, F.
Qu'est-ce qu'un chemin étiqueté par un mot w ?
Une suite d'arêtes consécutives portant successivement les lettres de w et partant d'un état initial.
Quand un automate accepte-t-il un mot w ?
S'il existe un chemin étiqueté par w allant d'un état initial à un état acceptant.
Comment se définit le langage L(A) d'un automate A ?
L'ensemble des mots w qu'A accepte, soit L(A)={w∈Σ* | A accepte w}.
Pourquoi un mot peut-il être refusé par un automate ?
Parce qu'un chemin existe sans aboutir à un état acceptant ou parce qu'aucun chemin ne porte ce mot.
Qu'impose un automate déterministe sur ses états initiaux ?
Il possède exactement un état initial.
Quelle condition doit respecter chaque état et lettre dans un automate déterministe ?
Il existe au plus une arête sortante étiquetée par cette lettre.
Qu'est-ce qu'un automate non déterministe ?
Un automate qui ne respecte pas les conditions du déterminisme.
Quand un mot est-il accepté dans un automate non déterministe ?
Dès qu'il possède au moins un chemin acceptant.
Combien de chemins étiquetés par un mot peut avoir un automate déterministe ?
Au plus un chemin étiqueté par ce mot.
Qu'est-ce qu'un automate complet ?
Un automate où chaque état a au moins une arête sortante pour chaque lettre.
Quelle différence y a-t-il entre un automate complet et un déterministe concernant les chemins étiquetés ?
Un complet a au moins un chemin pour chaque mot, un déterministe au plus un.
Qu'est-ce qu'une transition spontanée dans un automate ?
Une transition étiquetée par ε empruntée sans lire de lettre d'entrée.
Que fait l’algorithme de complétion dans un automate ?
Il ajoute un état puits non acceptant avec une boucle pour chaque lettre et redirige les arêtes manquantes vers lui.
Que garantit le théorème de Kleene pour toute expression régulière ?
Il existe un ε-NFA dont le langage est celui de l’expression régulière.
Que construit l’algorithme de Thompson pour une expression régulière ?
Un ε-NFA avec un unique état initial et un unique état acceptant distinct.
Combien d’états possède l’automate de Thompson pour une expression avec n symboles ?
Il possède exactement 2n états.
Qu’est-ce que la fermeture ε avant d’un état q ?
L’ensemble des états atteignables depuis q par des transitions ε, incluant q.
En quoi consiste la suppression arrière des transitions ε ?
À ajouter des arêtes pour chaque motif ε suivi d’une lettre, puis supprimer toutes les transitions ε.
Comment fonctionne un algorithme itératif de point fixe ?
Il construit une suite croissante d’ensembles et s’arrête quand un ensemble est stable.
Qu'est-ce que la fermeture epsilon avant ε_A^forward(q) ?
L'ensemble des états atteignables depuis q par des transitions ε uniquement.
Comment commence le calcul itératif de la fermeture epsilon ?
Il initialise chaque cellule avec l'état q et ses successeurs immédiats par ε.
Quand s'arrête le calcul itératif de la fermeture epsilon ?
Lorsque deux colonnes successives sont identiques.
Quelle transition crée-t-on pour chaque p dans ε_A^forward(q) et chaque transition p x→_A r ?
Une transition q x→ r dans l'automate sans transitions ε.
Que doit-on faire si un état acceptant r appartient à ε_A^forward(p) ?
Déclarer p acceptant dans l'automate sans transitions ε.
Que possède tout ε-NFA A sur l'alphabet Σ ?
Un NFA équivalent A′ sur Σ avec le même nombre d'états.
Teste tes connaissances avec un QCM de 65 questions sur Théorie des langages rationnels.
1. Comment définit-on un langage en théorie des langages ?
2. Quelle propriété caractérise un alphabet ?
Révisez le cours complet dans la fiche de révision de Théorie des langages rationnels.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards