Université Bordeaux I
Licence Informatique TD OMI 2001


Feuille d'exercices 1
Corrigé de l'exercice 13




Calcul des résiduels pour le langage L = a*ba + b*aba:
(epsilon)-1L = L     = Q0
a-1L = a*ba     = Q1
b-1L = a + b*aba     = Q2
(aa)-1L = a*ba = (aa+)-1L = Q3
(ab)-1L = a = (a+b)-1L = Q4
(ba)-1L = ba + epsilon     = Q5
(bb)-1L = b*aba = (bb+)-1L = Q6
(aba)-1L = epsilon     = Q7
(abb)-1L = Ø     = p
(baa)-1L = Ø     = p
(bab)-1L = a     = Q4
(bba)-1L = ba = (bb+a)-1L = Q8
(baba)-1L = epsilon     = Q7
(bbaa)-1L = Ø     = p
(bbab)-1L = a     = Q4

p est l'état ``puits''.
L'état initial est Q0 =(e)-1L, les états terminaux sont tous les Qi contenant epsilon.


This document was translated from LATEX by HEVEA.