Alphabets, mots, langages
Le vocabulaire des langages formels : alphabet, mot, mot vide, longueur, concaténation, puissance, miroir, préfixe, suffixe, facteur, langage, Σ* et étoile de Kleene, avec des calculs sur des langages finis.
- 27 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Comprendre
Quelques cartes du deck
Alphabet : de quoi s'agit-il ?
Voir la réponse
Ensemble fini de symboles, noté Σ, avec lesquels on écrit les mots : Σ = {a, b} ou Σ = {0, 1}.
Un mot est toujours un mot sur un alphabet donné : le même texte n'est pas un mot sur {a, b} et en est un sur {a, b, c}.
Avec u = ab et v = ba, que vaut vu ?
- baab
- abba
- baba
- aabb
Voir la réponse
baab
vu écrit v puis u : ba puis ab donne baab. La concaténation n'est pas commutative, uv = abba est un autre mot.
Un … sur un alphabet Σ est une partie de …, l'ensemble de tous les mots finis sur Σ.
Voir la réponse
Un langage sur un alphabet Σ est une partie de Σ*, l'ensemble de tous les mots finis sur Σ.
Σ* est le plus grand langage sur Σ ; tous les autres en sont des parties, de ∅ jusqu'à Σ* lui-même.
Mot vide ε : de quoi s'agit-il ?
Voir la réponse
Le mot de longueur 0, qui ne contient aucune lettre ; il est l'élément neutre de la concaténation.
Pour tout mot u, uε = εu = u. Il appartient à tout Σ* et ne se confond ni avec une lettre ni avec le langage vide.