automate des etas infini

A^2iB^3i<==>A^2iB^2iB^i
donc en resoud A^2iB^2i comme si A^iB^i

1-)à chaque lecture d'un A(avec A ou $(epsilon)en sommet de pile)==>empiler A sans changé d'etat(E0:etat initial).(BOUCLE)

2-)à chaque lecture d'un B avec A en sommet de pile ET à partir de l'etat E0 ==>Dépiler le A et passer à l'etat E1

3-)à chaque lecture d'un B(avec A en sommet de pile)==>depiler A sans changé d'etat(E1).(BOUCLE)

4-)ensuite on la pile vide et des B^i dors la pile encommence a absorber les B restante (#s1B->s1)

Citation:

---

C->C and C/C or C...
...
quoi que dans ce cas il est préférable d'utiliser un analyseur LL ou LR

---

Ici avec une gramaire récursive gauche, ça ne peut être qu'une analyse LR.

rukia-san, je ne vois pas trop ce que tu cherches, si tu veux des exemples de Langages non-régulier, tu prends tous les langages qui font une supposition sur le nombre de terminaux, et tu fais une comparaison :

Citation:

---

A^n B^p avec n > p
A^n B^p C^q avec n + p + q = 30
...

---

Programmer une grammaire bien spécifique n'a pas tellement d'intérêt, le mieux, c'est de programmer quelque chose de générique comme je te l'ai déjà proposé.

Citation:

---

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

---

Oui c 'est vrai j'avais pas vu les choses comme ça!
mais si par exemple on avait A^3iB^2i,ce ne serai pas le même principe

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:

---

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:

---

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:oops:
peux tu me donner des exemple?:oops: :oops:

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 ...).

Citation:

---

Envoyé par rukia-san

A^2iB^3i<==>A^2iB^2iB^i
donc en resoud A^2iB^2i comme si A^iB^i

1-)à chaque lecture d'un A(avec A ou $(epsilon)en sommet de pile)==>empiler A sans changé d'etat(E0:etat initial).(BOUCLE)

2-)à chaque lecture d'un B avec A en sommet de pile ET à partir de l'etat E0 ==>Dépiler le A et passer à l'etat E1

3-)à chaque lecture d'un B(avec A en sommet de pile)==>depiler A sans changé d'etat(E1).(BOUCLE)

4-)ensuite on la pile vide et des B^i dors la pile encommence a absorber les B restante (#s1B->s1)

---

Excuse moi, mais où t'assures tu que tu n'absorbe que i B à la fin ? J'ai l'impression que ton automate marche pour A^2iB^2iB* ?

--
Jedaï

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

Code:

---

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

---

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

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

Citation:

---

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)

@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.

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.

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