Nous avons vu que les automates reconnaissent les langages qui peuvent être engendrés
par les grammaires régulières.
Le problème : peut-on décrire un dispositif plus général, associé de manière naturelle
aux grammaires algébriques ?
Rappelons un exemple simple, sur l’alphabet S = {a, b}. Il est très facile d’écrire une
grammaire algébrique qui engendre le langage L = {an bn : n ³ 0 } ; il suffit pour cela de
considérer la grammaire S ? aSb | ? . Néanmoins, le Lemme de l’Etoile (cf. [1] ) nous
permet de prouver que L ne peut pas être engendré par une grammaire régulière. L’idée
intuitive est qu’avec une grammaire régulière, les symboles sont écrits consécutivement
(de gauche à droite), et qu’il faut donc compter les symboles a au fur et à mesure qu’on
les écrit, pour pouvoir ensuite les faire suivre d’autant de symboles b . Un dispositif qui
reconnaît L doit être capable de mémoriser. En fait, il suffira de coupler un automate à
une mémoire rudimentaire (une pile, supposée de capacité illimitée). Voici un tel exemple.
L’automate représenté ci-dessous est assorti d’une pile, vide au départ. En parcourant
l’automate, on empile un jeton à chaque passage par la transition d’étiquette a , et on
dépile un jeton – on doit pouvoir le dépiler – en passant par une transition d’étiquette b .
On laisse la pile inchangée par la transition d’étiquette ? (vide) de s0 à l’état 1 . Pour
qu’une chaîne testée wÎ{a, b}* soit acceptée, on convient que la pile doit être de nouveau
vide lorsque w est entièrement lue, en arrivant à l’état final. Il est facile de se convaincre
que le langage reconnu est L = {an bn : n ³ 0 }. Téléchargement de cours gratuit Automates épiles et grammaire algébrique cours pour particulier a télécharger et a consulter cours a distance Automates épiles et grammaire algébrique Mathematique cours en ligne éxercices et leçons pour téléchargement gratuit Automates épiles et grammaire algébrique
Recherche de Cours et ebooks 
Date: 10-02-2012
Mettre ce cours sur votre site ou Blog
Par : Rafik 
Note de cours: 
Mettre ce cours sur un forum 
Conseil de Rafik: Bon cours 
Rubrique: Mathematique
Lien de la page du cours 
Format du fichier :PDF
Taille du fichier: 231 Ko
Envoyer le cours a un ami (e) 
Télécharger le cours gratuitement