POA
- TD2+ : Automates
Le code ci-joint comprend deux
paquetages : automaton et regexp.
Le paquetage automaton permet de représenter des
automates non déterministes. Ces automates acceptent en
particulier les epsilon-transitions (transition pouvant être
franchie sans lire de symbole dans le mot à reconnaître).
Le paquetage regexp doit permettre de construire un
automate non déterministe à partir d'une expression
régulière préfixe composée des
opérateurs | (ou), * (itération) et .
(concaténation).
Une classe de test complète la distribution.
L'objet du TD est de compléter le code de la classe AutomatonBuilder
(remplacer les "..."). La construction de l'automate se fera à
l'aide de la structure AutomatonData, une instance de NotDeterministicAutomaton
étant difficilement modifiable. De plus, les états seront
des regexp.StateImpl, ce qui permet de statuer sur leur
statut initial ou terminal au moment de la création effective de
l'automate.
Pour construire l'automate, il est nécessaire de définir
l'automate obtenu selon l'opération traitée :
- Concaténation (symbole .)
Si A1 est l'automate (c'est à dire une instance d'AutomatonData)
obtenu à partir d'une expression exp1 et A2 celui obtenu
à partir d'une expression exp2, l'automate de . exp1 exp2 sera
composé de :
- comme états initiaux :
- l'ensemble des états initiaux de A1
- comme états terminaux :
- l'ensemble des états terminaux de A2
- comme transitions, l'union de :
- l'ensemble des transitions de A1,
- l'ensemble des transitions de A2,
- un nouvel ensemble d'epsilon-transitions entre chaque
état terminal de A1 et chaque état initial de A2.
- Ou (symbole |)
Si A1 est l'automate (c'est à dire une instance d'AutomatonData)
obtenu
à partir d'une expression exp1 et A2 celui obtenu à
partir d'une
expression exp2, l'automate de | exp1 exp2 sera composé de :
- comme états initiaux, l'union de :
- l'ensemble des états initiaux de A1
- l'ensemble des états initiaux de A2
- comme états terminaux, l'union de :
- l'ensemble des états terminaux de A1
- l'ensemble des états terminaux de A2
- comme transitions, l'union de :
- l'ensemble des transitions de A1,
- l'ensemble des transitions de A2
- Itération (symbole *)
Si A est l'automate (c'est à dire une instance d'AutomatonData)
obtenu
à partir d'une expression exp, l'automate de * exp sera
composé de :
- comme états initiaux
- comme états terminaux
- comme transitions, l'union de :
- l'ensemble des transitions de A,
- un nouvel ensemble d'epsilon-transitions reliant e à
chaque état initial de A
- un nouvel ensemble d'epsilon-transitions reliant chaque
état terminal de A à e