Haut de page
Validation de l'alphabet.
Préambule
Un alphabet ∑ est normalement un ensemble de caractère fini.
Mais pour réduire la taille des automates vis à vis des ensembles de caractères négatifs (considérés comme infini...), il sera composé:
- d'atome ∈ A , A = { a, \n, \t, +, ... }
- d'ensemble de caractères ∈ CC , CC = { [a-z], \w, \d, ... }
- d'ensemble négatif de caractère ∈ NCC , NCC = { [^a-z], \W, \D, ... } ce sont des ensembles infinis.
- du symbole ANY : n'importe quel caractère. deprecié
Pour rendre déterministe les automates,
il est nécessaire qu'un caractère soit présent que dans un et un seul symbole de l'alphabet :
les symboles doivent être distinct.
Cette opération est appellée ici la validation de l'alphabet (il faut bien que je lui donne un nom!).
Lorsqu'un symbole est remplacé par plusieurs autres :
- On crée des transitions avec les nouveaux symboles et depuis les transitions de l'ancien symbole.
- On efface l'ancien symbole ainsi que ses transitions.
Symboles mathématiques utilisés
| A ∩ B = ∅ |
A ∩ B ≠ ∅ |
| A |
B |
| Négation |
|---|
| ¬A |
¬B |
| Intersection |
|---|
| A∩B |
¬(A∩B) |
| Union |
|---|
| A∪B |
¬(A∪B) |
| Différence |
|---|
| A–B |
B–A |
| AΔB |
|
| A |
B |
| Négation |
|---|
| ¬A |
¬B |
| Intersection |
|---|
| A∩B |
¬(A∩B) |
| Union |
|---|
| A∪B |
¬(A∪B) |
| Différence |
|---|
| A–B |
B–A |
| AΔB |
|
- ∃ : il existe
- ∃! : il existe un et un seul
- ∈ : appartient à
- ∉ : n'appartient pas à
- ∀ : quelque soit
- ∅ : ensemble vide
- ≠ : différent de
- = : égale à
- |NCC| : nombre d'élément dans l'ensemble NCC.
|
Si il n'y a qu'un ensemble négatif de caractère, on peut passer l'étape suivante.
Cependant, il faut ajouter son opposé dans les ensembles de caractères (Au cas où le symbole ANY est utilisé).
Réduction de NCC
L'ensemble NCC contient les ensembles de caractère négatif.
Ces ensembles doivent être distinct: il n'en restera plus qu'un (|NCC|=1).
Il restera à le réduire vis à vis des autres éléments de l'alphabet.
|
∀ G1, G2 ∈ NCC, G1 ≠ G2
|
si ¬ G1 ∩ ¬ G2 = ∅ alors
G1 ⇔ Ginter ∪ ¬ G2
G2 ⇔ Ginter ∪ ¬ G1
avec Ginter = G1 ∩ G2
|
si ¬ G1 ∩ ¬ G2 ≠ ∅ alors
G1 ⇔ Ginter ∪ ( ¬ G2 – ¬ G1 )
G2 ⇔ Ginter ∪ ( ¬ G1 – ¬ G2 )
avec Ginter = G1 ∩ G2
|
Si G1=[^a-z] et G2=[^A-Z]
- [a-z] ∩ [A-Z] = ∅
- [^a-z] ⇒ Ginter ∪ [A-Z]
- [^A-Z] ⇒ Ginter ∪ [a-z]
- avec Ginter = [^a-zA-Z]
Alors on créé :
- un nouvel ensemble de caractère négatif : [^a-zA-Z]
- deux nouveaux ensembles de caractère : [a-z] et [A-Z]
Les transitions de G1 et G2 sont modifiées.
- 1 [^a-z]→ 3
-
1 [^a-zA-Z]→ 3
1 [A-Z]→ 3
|
- 2 [^A-Z]→ 4
-
2 [^a-zA-Z]→ 4
2 [a-z]→ 4
|
Les symboles G1 et G2 sont effacés.
|
Si G1=[^a-z] et G2=[^xyzAB]
- [a-z] ∩ [xyzAB] ≠ ∅
- [^a-z] ⇒ Ginter ∪ ( [xyzAB] – [a-z] )
- [^xyzAB] ⇒ Ginter ∪ ( [a-z] – [xyzAB] )
- avec Ginter = [^a-zAB]
Alors on créé :
- un nouvel ensemble de caractère négatif : [^a-zAB]
- deux nouveaux ensembles de caractère : [AB] et [a-w]
Les transitions de G1 et G2 sont modifiées.
- 1 [^a-z]→ 3
-
1 [^a-zAB]→ 3
1 [AB]→ 3
|
- 2 [^xyzAB]→ 4
-
2 [^a-zAB]→ 4
2 [a-w]→ 4
|
Les symboles G1 et G2 sont effacés.
|
NCC vs CC
∃! G ∈ NCC
∀ Gi ∈ CC
|
Si G ∩ Gi ≠ ∅
G = G – Gi ∪ Ginter
Gi = Gi – G ∪ Ginter
avec Ginter = G ∩ Gi
|
Si G=[^a-z] et Gi=[xyz0-9]
- [^a-z] ∩ [xyz0-9] ≠ ∅ = [0-9]
- [^a-z] ⇒ [^a-z0-9] ∪ Ginter
- [xyz0-9] ⇒ [xyz] ∪ Ginter
- avec Ginter = [0-9]
Alors :
- on divise l'ensemble de caractère en deux : [xyz] et [0-9]
- on remplace l'unique ensemble de caractère négatif par [^a-z0-9]
Les transitions de G et Gi sont modifiées.
- 1 [^a-z]→ 3
-
1 [^a-z0-9]→ 3
1 [0-9]→ 3
|
- 2 [xyz0-9]→ 4
-
2 [xyz]→ 4
2 [0-9]→ 4
|
Les symboles G et Gi sont effacés.
|
NCC vs Atoms
L'ensemble négatif de caractère sera considéré sous sa forme finale après cette étape.
∃! G ∈ NCC
∀ a ∈ A
|
Si a ∈ G
G = G – {a} ∪ {a}
|
Si G=[^a-z] et a=0
- 0 ∈ [^a-z]
- [^a-z] ⇒ [^a-z0] ∪ [0]
On remplace l'unique ensemble de caractère négatif par [^a-z0]
Les transitions de G sont modifiées.
- 1 [^a-z]→ 3
-
1 [^a-z0]→ 3
1 0→ 3
Le symbole G est effacé.
|
Décomposition de CC
L'ensemble CC contient les ensembles de caractère.
|
∀ G1, G2 ∈ CC, G1 ≠ G2
|
si G1 ∩ G2 ≠ ∅
G1 ⇒ Ginter ∪ ( G1 – Ginter )
G2 ⇒ Ginter ∪ ( G2 – Ginter )
avec Ginter = G1 ∩ G2
|
Si G1=[xyzAB] et G2=[A-Z]
- [xyzAB] ∩ [A-Z] ≠ ∅
- [xyzAB] ⇒ Ginter ∪ ( [xyzAB] – Ginter )
- [A-Z] ⇒ Ginter ∪ ( [A-Z] – Ginter )
- avec Ginter = [AB]
Alors on créé trois nouveaux ensembles de caractère :
- Ginter = [AB]
- ( [xyzAB] – Ginter ) = [xyz]
- [A-Z] – Ginter ) = [C-Z]
Les transitions de G1 et G2 sont modifiées.
- 1 [xyzAB]→ 3
-
1 [xyz]→ 3
1 [AB]→ 3
|
- 2 [A-Z]→ 4
-
2 [C-Z]→ 4
2 [AB]→ 4
|
Les symboles G1 et G2 sont effacés, car G1 ⊄ G2 et G2 ⊄ G1.
|
Si G1=[xyzA-Z] et G2=[A-Z]
- [xyzA-Z] ∩ [A-Z] ≠ ∅
- [xyzA-Z] ⇒ Ginter ∪ ( [xyzA-Z] – Ginter )
- [A-Z] ⇒ Ginter ∪ ( [A-Z] – Ginter )
- avec Ginter = [A-Z]
Alors on créé deux nouveaux ensembles de caractère car G2 ⊂ G1
- Ginter = [A-Z]
- ( [xyzA-Z] – Ginter ) = [xyz]
[A-Z] – Ginter ) = ∅
Les transitions de G1 et G2 sont modifiées.
- 1 [xyzA-Z]→ 3
-
1 [xyz]→ 3
1 [A-Z]→ 3
|
2 [A-Z]→ 4 -
2 [A-Z]→ 4
2 ∅→ 4
|
Le symbole G1 est effacé car G1 ⊄ G2.
Le symbole G2 est conservé car G2 ⊂ G1.
|
CC vs Atoms
|
∀ Gi ∈ CC, a ∈ A
|
si a ∈ Gi alors on modifie Gi
Gi ⇒ ( Gi – {a} ) ∪ {a}
|
Si Gi=[xyzA] et a=A
- A ∈ [xyzA]
- [xyzA] ⇒ [xyz] ∪ [A]
Les transitions de Gi sont modifiées.
- 1 [xyzA]→ 3
-
1 [xyz]→ 3
1 A→ 3
|
Le symbole Gi est effacé.
|
Le symbole ANY deprecié
Le symbole ANY, représentant n'importe quel caractère, sera définitivement supprimé.
Ses transitions seront multipliées au minimum par deux...
Si l'alphabet ∑ = {ε,ANY} ou {ANY}.
Le symbole ANY est remplacé par [^a] et a (au hasard!).
|
Sinon le symbole ANY est remplacé par tous les autres symboles de l'alphabet ∑. C'est à dire :
- l'ensemble des atomes,
- des ensembles de caractère,
-
et l'ensemble de caractère négatif.
(Si il n'existe pas, il est créé depuis les atomes et les ensembles de caractères)
|
Conclusion
Au final on a :
- ∃! G ∈ NCC
Il n'existe plus qu'un ensemble négatif de caractère (|NCC|=1).
- ∀G ∈ NCC , ∀G1 ∈ CC , G ∩ G1 = ∅
Il n'y a plus d'intersection entre l'ensemble de caractère négatif et les ensembles de caractères.
- ∀G ∈ NCC , ∀a ∈ A , a ∉ G
Il n'y a plus d'intersection entre l'ensemble de caractère négatif et les atomes.
- ∀G ∈ CC , ∀a ∈ A , a ∉ G
Il n'y a plus d'intersection entre les ensembles de caractères et les atomes.
- ∀G1 ∈ CC , ∀G2 ∈ CC , si G1 ≠ G2 alors G1 ∩ G2 = ∅
Il n'y a plus d'intersection entre les ensembles de caractères.
- Le symbole ANY n'est plus utilisé.