COMO DEFINIR EL AUTÓMATA FINITO QUE ACEPTA EL LENGUAJE COMPLEMENTARIO DE OTRO AUTÓMATA FINITO

 

     Cojamos el siguiente autómata, el cual, para el alfabeto S ={a, b, c} reconoce la cadena c, la cadena a, las cadenas que empiezan por a y acaban en a o en b y las que empiezan por a, seguidas de una serie de a o de b y acaban en c. Su diagrama determinista será:

 

     Para convertir este autómata en otro que acepte le lenguaje complementario se realizan los siguientes cambios:

  • Primero hay que comprobar si el diagrama esta totalmente definido; si no es así (que no aparezcan algunas transiciones), hay que convertirlo a uno que lo esté como ya se vio anteriormente.

  • Para cada uno de los estados de L(M) que eran de aceptación, no lo serán en L(M')
  • Para cada uno de los estados de L(M) que no eran de aceptación, en L(M') lo serán.

 

volver

 

© 1999 Roberto de la Fuente López. Todos los derechos reservados

Fecha de actualización: 15 de abril de 1999