Discussion :

[Rukia]

il ya 2 type d'automate a pile ::
1/les automate a pila vide (a la fin de le generation du mot la pile reste vide )
2/les automate a etas pres (a la fin de le generation du mot la pile ne reste pas vide)
ds votre exemple "" A^3iB^2i ""en utilise le 2éme type*

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
#SA->#AS 
ASA-AAS
 ASB->S1
 AS1B->S1

c'est le méme principe que mon langage A^iB^i sauf que dans la pile il ya des A a la fin

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
PRomu@ld
Essaie de faire un truc générique, en entrée tu prends un langage, et tu construis l'automate associé.

merci pour le conseil et c'est trés interssant mais j'ai pas bien saisie
peux tu me donner des exemple?

[PRomu@ld]

En fait, tu cherches à faire un programme qui analyse et te dis si un mot appartient à un langage ou pas. Mais ceci pour un seul langage.

Ce qu'il faudrait faire, pour que ça soit intéressant, c'est de faire une chose générique qui fonctionne quelque soit le langage. (en gros ça peut revenir à coder bison/yacc ...).

[Rukia]

ahh tu veux dire qu'il faut assure qu'il absorbe un nombre i de B
oui t'as raison ma solution et pour un nombre indeterminer de B
mais comment fair pour assurer le nombre i ??

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

en gros ça peut revenir à coder bison/yacc ...).

j'ai aucune idéé
qui peux me donner des exemple ???
merci d'avance

[b_reda31]

salut,
l'empilement des A doit se faire en alternance avec deux etats E0,E1(E0=>E1=>E0) afin de s'assurer qu'il y a un nombre paire de A,donc aprés la lecture de tous les A on doit avoir (2*i) A dans la pile.Ensuite vient le probléme des B,ici c'est presque le même principe sauf que on doit utiliser 3 etats alternativement (E0=>E2=>E3=>E0) en faisant la lecture de 3 B avec depilement seulement de 2 A.
est ce claire ?je peux te donner le bout de code pour faire ça mais ce n'est pas la même notation que l'on utilise

[PRomu@ld]

j'ai aucune idéé
qui peux me donner des exemple ???
merci d'avance

En fait, ce que tu veux peut être difficile à coder avec un automate à état fini (ou infini mais c'est n'est absolument pas représentable complètement en machine). Il faut passer à un niveau supérieur, c'est à dire les grammaires, les automates LR (LR(0), LR(1), ...), les automates LaLR, etc ... . Ces structures permettent de résoudre des problèmes que tu ne peux pas résoudre avec des automates classiques, c'est à dire reconnaître des langages non rationnels mais algébriques (par exemple). C'est un niveau d'abstraction plus élevé qui te permet de résoudre des problèmes que tu ne peux résoudre avec des automates LL.

Beaucoup (tous ?) de langages de programmations peuvent être générés à l'aide de générateurs comme bison (LaLR), avoir un outil qui te permet de faire ceci est une chose relativement puissante (et intéressante pédagogiquement), si tu as l'occasion de regarder comment fonctionnent bison/yacc c'est très instructif (table des items LR(0), table d'action, ... ). Mais à part le coté pédagogique, une fois que tu as compris comment cela fonctionne, le plus intéressant (en tout cas de mon point de vue) est la production de code (code intermédiaire et code cible), parce que réinventer la roue (bison/yacc sont des outils bien conçus, fiables et performants) n'a pas de sens mais adapter la reconnaissance de ton langage à un langage (ou machine) cible est relativement intéressant (et utile par la même occasion)

[Rukia]

@reda_b
on dépile 2 A par 3 B ça c'est l'idéal mais comment tu peux le faire?
en plus pourquoi utilises-tu 2 états, or ... un seul état suffit pour empiler les A.
donne moi le code; je vais essayer de comprendre ta notation.
et si tu peux me donner des commentaires à coté, ça sera mieux.
et merci pour ton aide.

@ PRomu@ld
merci beaucoup pour cette définition, maintenant j'ai compris.

[b_reda31]

Salut,je t'explique la notation que j'utilise.Une transition s'ecrit en général sous la forme suivante:
T(Ei,x,X)=(Ej,Y) oû:
-x est le caractére lu.
-X est le sommet de pile avant transition.
-Y est le sommet de pile aprés transition.
-Ei,Ej sont les etats de départ et d'arrivé.
cette instruction s'interpréte comme suit:
La lecture du caractere "x" à partir de l'etat Ei en ayant X en sommet de pile ,transite vers l'etat Ej en remplaçant X par Y dans la pile.
Il y a bien sur des cas particuliérs:
Lecture sans toucher à la pile(X=Y),ou bien changement d'etat sans lecture(x=$)...etc

revenons à notre exemple maintenant:A2i B3i.Initialement la pile est vide donc on a 'D'(symbole fond de pile) en sommet.
Pour s'assurer qu'on lit un nombre paire de A on utilise deux etats:

T(E0,A,D)=(E1,AD) //lecture de A tout en l'empilant et changement d'etat.

T(E0,A,A)=(E1,AA) //meme chose sauf qu'ici la pile etait pas vide.

T(E1,A,A)=(E0,AA)//lecture de A tout en l'empilant et changement d'etat.

De cette façon on est sur qu'à l'etat E0 le nombre de A est toujours paire(ou eventuelement nul),le premier B se lira donc à l'etat E0

T(E0,B,A)=(E2,$)//Lecture d'un B en depilant le A etant au sommet de pile.
T(E2,B,A)=(E3,$)//Lecture d'un B en depilant le A etant au sommet de pile.
T(E3,B,A)=(E0,A)//Lecture d'un B sans toucher au A etant au sommet de pile.
on a donc lu 3 B tout en dépilant 2 A.

Si la pile est vide le mot est reconnu par l'automate :
T(E0,$,D)=(Etat-finale,D),ici on remarque que $ appartient au langage.

[Rukia]

désole pour le retard
et mici pour t'as reponse

[Rukia]

pour langage A^2iB^3i

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
#SA->#AS
ASA-AAS
ASB->S1
AS1B->S1
#s1B->s1

c'est le méme principe que mon langage A^iB^i sauf qu'on absorbe tous les B restante

[b_reda31]

est tu certain(e) de ta solution??
ici tu as plusieurs contraintes:
-Le nombre de A est pair
-Le nombre de B est multiple de 3
-Le nombre de B depend directement du nombre de A
avec la notation que j'utilise il y a beaucoup plus de lignes...
faut t'assurer que pour chaque lecture d'une pair de A tu doit avoir trois B

[PRomu@ld]

proposer moi un langage algébrique pour le programmer

Essaie de faire un truc générique, en entrée tu prends un langage, et tu construis l'automate associé.