et l'automate de L1' 
Question – Trouver l'expression régulière, l'automate déterministe et la grammaire de type 3 (dans n'importe quel ordre) pour le language tel que :
si (# a mod 3 = 0) alors (# b mod 2 = 1) sinon (# b mod 2 = 0)
Réponses
En français, le langage s'énonce ainsi : si le nombre de a est multiple de 3 alors le nombre de b est impair, sinon le nombre de b est pair.
La meilleur approche est d'abord de construire l'automate déterministe. Le faire "d'un coup" est difficile. Par contre, on peut facilement le construire en décomposant les propriétés du language.
Automate . On commence par L1 ayant un nombre de a multiple de 3. L1' est le complementaire de L1 (le nombre de a n'est pas multiple de 3).
L'automate de L1 et l'automate de L1'
Soit L2, le langage ou le nombre de b est pair et L2' son complémentaire. Nous avons les deux automates pour L2 et L2'
On pose L3 = L1 inter L2' et L4 = L1' inter L2. Attention, L4 n'est pas le complementaire de L3. Nous avons les deux automates pour L3 et L4 :
L est alors l'union entre L3 et L4. ceci se construit facilement au niveau des automates. D'une façon générale, l'union de deux automates se fait en rajouter un état initial qui se connecte avec des transitions epsilon aux état initiaux de chaucun des deux automates. Les états initiaux des deux automates ne sont plus initiaux. Cela donne :
On applique cela à L3 et L4. Ou augmente les transitions, par le fait qu'une transition epsilon A-->B suivie d'une transition standard B-->C peut-etre remplacée par une transition directe A-->C. Après augmentation, on peut supprimer les transitions epsilon (et es états éventuellement non atteignables - il n'y en a pas dans cet exercice). Voir le poly du cours pour plus de détails:
Après déterminisation (qui n'est ni difficile ni longue), on obtient l'automate recherché :
Grammaire . La grammaire de type 3, s'obtient par la traduction de l'automate. On renomme les états avec les symboles S0 à S6). On a pas gardé de règles avec epsilon (on ne se l'autorise que pour la source, en général).
S0 --> a S1 | a | b S2 | b
S1 --> a S3 | b S4
S2 --> a S4 | b S5
S3 --> a S5 | b S6
S4 --> a S6 | b S1 | b
S5 --> a S1 | a | b S2 | b
S6 --> a S2 | b S3
Expression régulière . De loin la partie la pus délicate (et longue) de l'exercice. On le fait par la méthode des équations. Poser les équations est équivalent à poser la grammaire (seule la manière d'écrire les choses change).
L0 = a L1 + b L2
L1 = a L3 + b L4 + eps
L2 = a L4 + b L5 + eps
L3 = a L5 + b L6
L4 = a L6 + b L1
L5 = a L1 + b L2
L6 = a L2 + b L3
Il faut trouver L1 et L2. On remplace L6 dans l'équation de L4
L4 = a L6 + b L1
L4 = a(a L2 + b L3) + b L1 = aa L2 + ab L3 + b L1
On remplace L6 et L5 dans l'équation de L3
L3 = a L5 + b L6
L3 = a (a L1 + b L2) + b (a L2 + b L3)
= aa L1 + ab L2 + ba L2 + bb L3
= aa L1 + (ab + ba) L2 + bb L3
L3 = (bb)*(aa L1 + (ab + ba) L2)
L4 = aa L2 + ab L3 + b L1
= aa L2 + ab(bb)*(aa L1 + (ab + ba) L2) + b L1
L4 = (aa + ab(bb)*(ab + ba)) L2 + (ab(bb)*aa + b) L1
en distribuant et simplifiant (un peu)
L4 = (aa + ab(bb)*ab + ab(bb)*ba)) L2 + (ab(bb)*aa + b) L1
= (ab(bb)*ab + a(bb)*a)) L2 + (ab(bb)*aa + b) L1
L2 = a L4 + b L5 + eps
L2 = a ((ab(bb)*ab + a(bb)*a)) L2 + (ab(bb)*aa + b) L1) + b (a L1 + b L2) + eps
= a(ab(bb)*ab + a(bb)*a) L2 + a(ab(bb)*aa + b) L1 + ba L1 = bb L2 + eps
= (aab(bb)*ab + aa(bb)*a + bb) L2 + (aab(bb)*aa + ab + ba) L1 + eps
L2 = (aab(bb)*ab + aa(bb)*a + bb)*((aab(bb)*aa + ab + ba) L1 + eps)
