Un automate pour les caractériser tous

Au début des années 2000, Okhotin a introduit deux familles de grammaires formelles, les grammaires conjonctives et les grammaires booléennes, qu’il présente comme “le véritable cas général des grammaires sans contexte”. Ces grammaires enrichissent les grammaires algébriques par l’ajout d’une opération de conjonction pour les grammaires conjonctives et de la négation en plus de la conjonction pour les grammaires booléennes. Ces deux nouvelles grammaires (et leurs restrictions linéaires) viennent ainsi étoffer la zoologie des classes de langages formels sans contexte. L’un des critères permettant de mesurer l’importance d’une classe de langages est qu’elle dispose d’une définition équivalente par une famille d’automates. On peut ainsi citer la caractérisation des langages réguliers par les automates finis, celle des algébriques par les automates à pile ou encore la caractérisation de la restriction linéaire des grammaires conjonctives par les automates treillis. Ces caractérisations nous permettent de mieux comprendre le pouvoir d’expression des grammaires mais ne facilitent pas forcément leur comparaison.

Dans cet exposé, je présenterai une famille d’automates, appelés automates SCYK, permettant d’obtenir une caractérisation uniforme des classes de langages citées. Cette famille d’automates est inspirée de l’algorithme classique pour la reconnaissance de langages algébriques découvert indépendamment par Sakai, Cocke, Younger et Kasami (d’où son nom). Dans leur version la plus générale, ces automates caractérisent exactement les langages booléens puis, en leur ajoutant différentes restrictions, ceux-ci nous permettent de caractériser naturellement les langages conjonctifs, algébriques (avec leurs restrictions linéaires) ainsi que les langages réguliers.