automate des etas infini

Rukia · 12/07/2007, 03h07

Bonjour
chui en vacance et je veux programmer un automate
qui peux me proposer un automte des etats infini ???
et avec quelle langage ???

Merci d avance

**PRomu@ld** · 12/07/2007, 15h40

Il faudra que tu détailles un peu plus ce que tu cherches, moi je verrai bien un AFD, c'est relativement simple à gérer.

Pour ce qui est du langage, tu n'es pas dans le bon forum, mais peu importe du moment que tu arrives à faire ce que tu veux avec.

**b_reda31** · 14/07/2007, 21h21

salut,
Personnelement je n'ai jamais entendu parler d'automate d'etat Infini mais plutot des automates d'etat fini (AEF) ce qui servent à reconnaitre des "Mots" de langages réguliers...Est ce de ça que tu parles??
si oui tu peux par exemple l'implémenter sous forme d'une matrice oû les etats sont en ligne et en collone ,l'intersection de ces deux derniers donne le caractere qui permet de passer de l'etat ligne vers l'etat collone(ou l'inverse si tu veux).
De cette façon tu pouras facilement appliquer les algorithmes de réduction,détérmination...etc,Pour ce qui est du langage si tu débutes en programmation je te conseil le Pascal (Turbo pascal ou delphi)

**PRomu@ld** · 14/07/2007, 22h08

si oui tu peux par exemple l'implémenter sous forme d'une matrice oû les etats sont en ligne et en collone ,l'intersection de ces deux derniers donne le caractere qui permet de passer de l'etat ligne vers l'etat collone(ou l'inverse si tu veux).

En fait, un Automate n'est qu'un graphe, alors toute représentation d'un graphe sera correcte pour un automate : matrice d'adjacence (pour les petits automates ou pour les automates denses), liste d'adjacence, ...

Rukia · 15/07/2007, 08h44

Envoyé par b_reda31

salut,
Personnelement je n'ai jamais entendu parler d'automate d'etat Infini

avec un automate d etat infini( automate a pile )tu peux géneré des langage regulier ou non regulier (les langage algébrique)

**PRomu@ld** · 15/07/2007, 08h56

avec un automate d etat infini( automate a pile )tu peux géneré des langage regulier ou non regulier (les langage algébrique)

Dans ce cas, il faudra peut-être te tourner vers les grammaires.

moi je veux que vous me proposer un langage(c n'est pas un langage de programmation )

Je n'arrive pas à comprendre ta question.

Rukia · 15/07/2007, 09h01

je veux dire un langage algébrique
par exemple L=A^iB^i , i>0

Rukia · 15/07/2007, 09h12

mici pour la reponse
pour le langage que j'ai proposé sont automate d'état infni (automate a pile )

Code :

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

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

S et S1 sont mes etats
ça c'est l automate a pile vide

moi je veux d autre propostion

**@min@** · 15/07/2007, 13h37

SI tu dis que S1 et S sont t'es etat alors ces des non -terminaux alors dans ce cas Y'a le "a" et non "A"et "b" non "B"

**b_reda31** · 15/07/2007, 16h32

Automate d'etat infini=automate à pile??
autant pour moi je ne le savais pas

Code :

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

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

je n'ai pas trés bien saisi ce bout de code...
ce n'est pas vraiment cette notation que j'utilise.Le principe pour le langage que tu as donné est le suivant:

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-)Lecture de $ à partir de l'etat E1 passe à l'état finale Ef

maintenant pour la notation ça depend des bouquins

Rukia · 15/07/2007, 16h43

Code :

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

[@min@]  SI tu dis que S1 et S sont t'es etat alors ces des non -terminaux alors dans ce cas Y'a le "a" et non "A"et "b" non "B"

mon alphabet c'est {A,B} et je ne suis pas obliger de prendre a,b

Code :

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

1
2
3
4
5
6
7
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-)Lecture de $ à partir de l'etat E1 passe à l'état finale Ef

oui c'est ça l idée de mon code

mais ma question ::
proposer moi un langage algébrique pour le programmer

**b_reda31** · 15/07/2007, 16h51

Tu veux dire un autre langage??
pourquoi il ne te plait pas celui que tu as choisis?

Rukia · 15/07/2007, 17h02

mon lanagage est simple tres simple juste empiler ensuite depiler
il ya juste 2 etape ds mon programme ""j'utilise une structure pile "
moi je veux un autre

**b_reda31** · 15/07/2007, 17h14

Un langage plus compliqué...Mmmm
y a A^iB^iC^i mais ce n'est pas un langage algebrique,mais un langage de type1 donc une seule pile ne suffira pas.
sinon en langage algébrique y a A^2iB^3i,tu poura commancé avec ça

Rukia · 15/07/2007, 17h59

avec les automate a pile (etat infini en resoud comme ça)
mais tes remarque si pour un langage regulier =>pour proposer un automate de robin scott
mais le langage que tu ma proposer c'est un langage non regulier

**b_reda31** · 15/07/2007, 20h51

peux tu me donner la signification des lignes de ton code?

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

j'allais te dire la même chose un truc du genre:
S->If C then S else S;/S;S/while C do S/begin S end...
C->C and C/C or C...
...
quoi que dans ce cas il est préférable d'utiliser un analyseur LL ou LR

Rukia · 15/07/2007, 21h25

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)

**PRomu@ld** · 16/07/2007, 08h53

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 :

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

**b_reda31** · 16/07/2007, 16h40

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

**Jedai** · 21/07/2007, 17h07

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ï