Skip to main content Informatique en prépa - Lycée Malherbe 

1- Langages

Les langages sont un outil pour étudier toutes sortes d'assemblages de caractères et de mots : du langage naturel aux chaines de nucléotides de l'ADN en passant par les laguages de programmation.

I. Définitions

Définition : alphabet

Un alphabet est un ensemble fini, en général de caractères.

Par exemple, ou sont des alphabets.

Dans la grande majorité des cas, le langage sera fixé en début de sujet et ne changera plus. Ce sera dans 99% des cas des langages simples :

  • , les nuclétides de l'ADN, lorsque les concepteurs du sujet veulent faire semblant d'avoir un lien avec un truc concret.
Définition : mot

On se donne un alphabet. Un mot sur est une suite finie d'éléments de .

On note le mot vide, et le mot (avec ).

On note l'ensemble des mots sur .

Par exemple, sur , est un mot.

Définition : préfixes, suffixes, facteurs

Si sont deux mot :

  • est un préfixe de si tel que .
  • est un suffixe de si tel que .
  • est un facteur de si tel que .
Définition : langage

On se donne un alphabet. Un langage sur est un ensemble (fini ou infini) de mots sur .

Toujours avec , les ensembles suivants sont des langages :

II. Opérations sur les langage

On définit des opérations sur les langages :

Par exemple : pour et , on a

Pour les langages définis précédemment, et , donnez les langages suivants :

Dans quel cas, pour un langage , a-t-on la propriété : $\forall L_2 \subset \Sigma^*, L_2 \subset L_1 L_2 $ ?

Lorsque ( étudier le cas où , vérifiable directement)

(difficile) Pour les langages définis précédemment, donnez .

  • est l'ensemble des mots de dans lesquels chaque est immédiatement précédé d'un (c'est-à-dire les mots qui ne commencent pas par et ne contiennent pas le facteur ).
  • (le mot vide est dans ).
  • .