cours-ir09

AutomatesNotions de baseNotes de cours, IR1, 2009Sylvain Lombardy1 Alphabets, mots, langagesUn alphabet A est un ensemble fini de symboles appel´es lettres.Un mot est une suite finie de lettres.∗On note A l’ensemble des mots que l’on peut former avec des lettres de l’alphabet A.∗Un langage sur un alphabet A est un ensemble (fini ou infini) de mots de A .Exemples :1. L’alphabet A permettant d’´ecrire les mots usuels comporte environ soixante-dix lettres (mi-1nuscules, majuscules, lettres accentu´ees). L’ensemble des mots du fran¸cais est un langage sur A .1∗Le mot carichon appartient `a A mais n’est pas un mot fran¸cais.12. Les s´equences d’ADN se repr´esentent sur un alphabet A ={G,A,T,C}. Une s´equence d’ADN2∗ ∗est un mot de A , mais un mot de A n’est pas forc´ement une s´equence correcte.2 23. On peut prendre comme alphabet A l’ensemble des mots du fran¸cais (plusieurs centaines de3milliers de mots). Un “mot” est alors une suite finie d’´el´ements de cet alphabet, c’est donc cequ’on appelle habituellement une phrase. Les phrases correctes sont un langage sur A .32 Automates non d´eterministesD´efinition Un automate (non-d´eterministe) A sur un alphabet A est d´efini par les ´el´ementssuivants :– un ensemble fini d’´etats not´e Q;– un ensemble fini E de transitions, chaque transition ´etant d´efinie par un ´etat de d´epart p, un´etat d’arriv´ee q et une ´etiquette a appartenant `a A; on note une telle transition (p,a,q).– un sous-ensemble de Q appel´e ...