Présentation

• La notion de complexité est restée longtemps intuitive: si chacun fait aisément la différence entre un objet simple (disons, le pinpon d'une sirène) et un objet compliqué (par exemple, un mouvement de quatuor à cordes), ce n'est que récemment que cette différence a reçu une définition rigoureuse (en fait, plusieurs). Ainsi, Gregory Chaitin a proposé de définir la complexité d'une suite de n bits, comme la taille minimale d'un programme écrivant cette suite.
• Dans le cas d'un langage rationnel, plusieurs points de vues sont possibles, puisqu'il existe diverses façons de décrire un tel langage: avec un expression rationnelle, ou avec un automate fini, déterministe ou non.
• Dans ce texte, nous définissons la complexité d'un langage rationnel L comme la taille minimale (en nombre d'états) d'un automate fini, déterministe, complet, reconnaissant L.
• Nous nous intéresserons à l'effet des opérations usuelles sur cette complexité: par exemple, si l'on connaît les complexités de deux langages rationnels L et M, que peut-on dire de la complexité de la réunion de ces deux langages?