Cette introduction, qui traite d'un sujet ancien et couvert par de
nombreux ouvrages, présente néanmoins des points de vue originaux ou
oubliés que je tiens à souligner :
- Arbres de dérivation
On introduit une notion de dérivation
indicée gauche et on démontre (quand beaucoup de livres se
contentent d'admettre)
qu'il y a une correspondance bijective entre les dérivations indicées gauches
et les arbres de dérivation.
- Automates finis
On sépare clairement la construction de
l'automate minimal et la preuve que cette construction produit l'automate
minimal. On donne de plus deux preuves assez différentes de l'unicité de
l'automate minimal.
- Systèmes d'équations
On montre que les règles de grammaire
peuvent être aussi vues comme des définitions inductives de langages et
suivant un résultat de
Bruno Courcelle on
donne une condition nécessaire et suffisante, calculable, pour qu'un
système d'équations ait une et une seule solution.
Dernière modification : 05-Nov-2010