Notions de base et propriétés d’un langage

Cours et notions de base et propriétés d’un langage, tutoriel langage de programmation en pdf.

CONCEPTS DE BASE

Un mot w est défini sur l’alphabet X est une suite finie et ordonnée, éventuellement vide, d’éléments de l’alphabet. C’est une concaténation de chiffres, de lettres ou de symboles appartenant à X. Le mot vide, noté ε correspond à la suite de symboles vide.
Exemple:
Un langage L défini sur l’alphabet X est un ensemble de mots défini sur l’alphabet en question. Cet ensemble de mots peut être fini comme il peut être infini.
Exemple:
Formellement, si X est un alphabet alors un langage sur X est par définition un sous ensemble du monoïde X* Exemple: soit x= {a, b, c} Problème: on cherche l’ensemble des mots qui commencent par a suivi de zéro ou plusieurs c et se terminent par bb.
Solution: Pour un alphabet fini X, le monoïde X* librement engendré par X est l’ensemble des suites finies u= u1u2…un où ui est une lettre de X et n désigne la longueur de u avec n>= 0. La loi de composition interne du monoïde X* est la concaténation. Si X = {a, b}, alors l’ensemble X* = {ε, a, b, aa, ab, bb, aab, bba, aba, aaa, bbb,…} L’élément neutre ε appelé aussi le mot vide est l’unique mot de longueur 0.

LE LANGUAGE

Un langage L défini sur l’alphabet X est un ensemble de mots défini sur l’alphabet en question. Cet ensemble de mots peut être fini comme il peut être infini.
Exemple: Formellement, si X est un alphabet alors un langage sur X est par définition un sous ensemble du monoïde X* Exemple: soit x= {a, b, c} Problème: on cherche l’ensemble des mots qui commencent par a suivi de zéro ou plusieurs c et se terminent par bb.
Solution: Pour un alphabet fini X, le monoïde X* librement engendré par X est l’ensemble des suites finies u= u1u2…un où ui est une lettre de X et n désigne la longueur de u avec n>= 0. La loi de composition interne du monoïde X* est la concaténation. Si X = {a, b}, alors l’ensemble X* = {ε, a, b, aa, ab, bb, aab, bba, aba, aaa, bbb,…} L’élément neutre ε appelé aussi le mot vide est l’unique mot de longueur 0.

……..