Automates finis : pourquoi certains langages leur échappent-ils ?

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Je suis très heureuse de vous retrouver pour cette nouvelle exploration. Et bon, pour commencer aujourd'hui, j'aimerais vous poser une petite devinette.

Intervenant 20:10

Allez-y, je vous écoute.

Intervenant 10:11

Alors, à votre avis, quel est le lien exact, le point commun vraiment fondamental entre le dictionnaire de la langue française, le code source d'un programme informatique que vous utilisez tous les jours et l'ADN qui se trouve à l'intérieur de nos cellules ?

Intervenant 20:29

C'est une excellente question pour démarrer et la réponse tient en un seul mot en fait. Un concept qui est abstrait mais extrêmement puissant, c'est la notion de langage.

Intervenant 10:41

Le langage, d'accord.

Intervenant 20:42

Voilà, le langage. Et l'objectif de notre plongée d'aujourd'hui, c'est justement de comprendre comment on peut manipuler mathématiquement ces langages. Grâce à ce qu'on appelle des machines abstraites. On va voir comment on les traite et surtout, on va découvrir les limites physiques et mathématiques de ces outils informatiques.

Intervenant 11:04

Ok, décortiquons un peu ça, parce que quand on utilise le mot « langage » dans la vie de tous les jours, on pense tout de suite à la communication, non ?

Intervenant 21:12

C'est ça, ouais.

Intervenant 11:13

On pense à Molière, à la poésie, ça implique du sens, de la sémantique. Mais j'imagine qu'en mathématiques ou en informatique théorique, on aborde la chose sous un angle beaucoup plus froid, non ?

Intervenant 21:23

Oui, complètement. C'est même le point de départ indispensable en fait.

Intervenant 11:26

On s'en fiche du sens, c'est ça ?

Intervenant 21:28

Exactement. Il faut totalement se détacher de l'idée de signification. Que le mot veuille dire quelque chose ou pas, ça n'a aucune importance.

Intervenant 11:35

Ah ouais ?

Intervenant 21:35

Ce qui compte, c'est la validité de sa construction. C'est sa structure.

Intervenant 11:40

D'accord.

Intervenant 21:41

Pour ça, on pose des définitions qui sont très rigoureuses. La première brique, vraiment le B à bas, c'est l'alphabet.

Intervenant 11:49

L'alphabet, OK. Comme A, B, C, D.

Intervenant 21:51

C'est ça. Dans notre contexte théorique, un alphabet, c'est tout simplement un ensemble fini de caractères.

Intervenant 11:59

Fini, donc ça veut dire qu'il a une

Intervenant 22:00

fin. Voilà, il y a un nombre précis d'éléments. Par exemple, si on prend l'ADN, l'alphabet génétique ne comporte que quatre lettres.

Intervenant 12:08

Ouais, les nucléotides, c'est ça. A, C, G et

Intervenant 22:12

T. Exactement. Quatre lettres. C'est fini. Mais en théorie pure, on peut imaginer un alphabet qui ne contiendrait que les lettres A, B et C.

Intervenant 12:21

Ok.

Intervenant 22:21

La seule règle stricte, vraiment la seule, c'est que cet ensemble de bases doit être fini. On ne peut pas avoir une infinité de caractères de bases.

Intervenant 12:30

Je vois. Donc si je file un peu la métaphore, l'alphabet c'est un peu comme une boîte de briques de construction quoi.

Intervenant 22:36

Ouais, c'est une très bonne image.

Intervenant 12:38

On a un nombre limité de formes et de couleurs, disons trois types de briques. Et ça, c'est notre ensemble fini. Ce sont nos caractères. Et à partir de là, j'imagine qu'on construit ce qu'on appelle des

Intervenant 22:50

mots.

Intervenant 12:51

C'est exactement ça. Un mot, dans ce cadre formel, c'est juste une suite finie de caractères qu'on va piocher dans notre alphabet.

Intervenant 22:58

D'accord, donc on les aligne.

Intervenant 13:00

Voilà. Si notre alphabet c'est juste A B C, on peut très bien construire le mot B B C

Intervenant 23:07

A. Ou alors le mot A A A.

Intervenant 13:10

Même si c'est imprononçable.

Intervenant 23:12

Ou A, C, B, C, peu importe. Qu'ils soient absents d'un dictionnaire classique, on s'en moque.

Intervenant 13:17

Ouais.

Intervenant 23:18

Mathématiquement, ce sont des mots valides puisqu'ils sont formés avec les bonnes lettres, c'est tout.

Intervenant 13:22

Donc, la brique, c'est la lettre. La petite tour que je construis en empilant genre 5 ou 10 briques, ça c'est mon mot.

Intervenant 23:29

C'est ça.

Intervenant 13:29

Mais alors, le langage lui-même, comment on le définit par rapport à tout ça ? Parce qu'on a les briques, on a les tours, mais le langage c'est quoi ?

Intervenant 23:36

Eh bien le langage, qu'on note souvent avec un L majuscule d'ailleurs, c'est un ensemble de mots. Des mots qui sont construits sur un alphabet donné et surtout qui respectent une règle précise.

Intervenant 13:47

Une règle, ok.

Intervenant 23:48

En gros, c'est la collection complète de toutes les tours de briques que vous acceptez de valider.

Intervenant 13:53

D'accord, donc il y a un filtre.

Intervenant 23:54

Voilà. Et il y a une subtilité mathématique majeure ici, c'est qu'on a dit que l'alphabet est fini.

Intervenant 13:59

Ouais.

Intervenant 24:00

On a dit que chaque mot a une longueur finie.

Intervenant 14:02

Oui, on s'arrête de construire la tour à un moment.

Intervenant 24:04

Exactement. Mais le langage, lui, la collection de ces mots, il peut très bien être un ensemble infini.

Intervenant 14:10

Attendez, infini. Mais comment c'est possible d'avoir un truc infini si on part d'un nombre fini de briques ?

Intervenant 24:15

Prenons un exemple simple.

Intervenant 14:17

Je veux bien.

Intervenant 24:18

Si on prend le dictionnal français, bon, c'est un langage fini.

Intervenant 14:21

Ouais, il y a, je sais pas, cent mille mots, mais c'est fini.

Intervenant 24:23

Voilà, il y a un nombre défini de mots acceptés à un instant T. Pareil pour, je sais pas, les commandes de base d'un logiciel.

Intervenant 14:31

Ok.

Intervenant 24:31

Mais si on bascule sur une règle plus abstraite, prenons un alphabet composé uniquement des lettres A et B. Juste deux lettres.

Intervenant 14:39

Ok, A et B.

Intervenant 24:41

Imaginons que notre règle de langage soit, disons, l'ensemble de tous les mots qui contiennent un nombre impair de la lettre A. Un nombre impair de A, ok. Ce langage, il va inclure le mot A, puisqu'il y en a un seul. Logique, c'est impair. Il va inclure le mot AAA. Oui, il y en a trois.