je sais qu'il est possible de déduire une automate à pile à partir d'une grammaire quelconque.
L'automate en question est non déterministe et compote un seul état et reconnait les mots par pile vide
Par contre, je ne suis pas certains d'avoir compris comment on le construit.
Admettons la grammaire qui engendre les palindromes de la forme
Soit par exemple quelques mots qui doivent être engendré par la grammaire et reconnu par le langage
c
aca
bca
abcba
bacab
etc etc
Une grammaire évidente permettant d'engendrer ces polynômes se formerait à partir des règles de productions suivante
P:
Quel serait donc l'automate à pile déduit de cette grammaire ?
Le cours me donne la fonction de transition delta telle que
delta(q,lambda,A) = (q,a) pour tout A -> a appartenant à P
delta(q,x,x) =(q,lambda) pour tout x appartenant à X
P représente les règles de production de la grammaire
lambda représente le mot vide
X représente l'alphabet de la grammaire, donc ici {a,b,c}
Dois je en déduire que mon automate est le suivant ?
delta(q,lambda,S) = (q,c)
delta(q,lambda,S) = (q,aSa)
delta(q,lambda,S) = (q,bSb)
delta(q,a,a) =(q,lambda)
delta(q,b,b) =(q,lambda)
delta(q,c,c) =(q,lambda)
C'est ce que je pense comprendre de mon cours, mais j'en suis pas sûr du tout...si vous aviez quelques éclaircissements, ce ne serait pas de refus =)
Merci !