martes, 6 de noviembre de 2012

Expresion

Esta es mi expresion

L = {x Î {0, 1}* x no contiene ‘00’}
(0 + 1)* 00 (0 + 1)*® Expresión regular del L que contiene ‘00’
(1 + 01)* (0 + l) ® Expresión regular del L que no contiene ‘00’
Los estados 1 y 4 se pueden unir en uno solo.

Se pueden suprimir las transiciones d  (3, 0) = 3 yd  (3, 1) = 3. La idea es que, una vez que M cae en el estado 3, la palabra leída Ï L y, además, cualquier palabra formada por la concatenación la palabra leída, como prefijo, con cualquier x Î S*, como cola, tampoco pertenece a L. Entonces, ¿para qué seguir leyendo?. Una vez suprimidas las dos flechas de salida del estado 3, M queda así:



Qué hace M cuando lee una letra y está en 3?  Nada.

 Queda parado, bloqueado. La función de transición, para la situación de bloqueo, es d(3, 0) = Æ y d(3, 1) =  (subconjunto de estados vacío). Cuando se llega al estado 3 hay situación de bloqueo para " a Î S; S = {0, 1}.

Es un caso parecido al procesador de una computadora. Cuando el Registro de Instrucciones de la Unidad de Control alberga en la parte CO (Código de Orden) una configuración que no forma parte del repertorio de instrucciones, la máquina queda bloqueada al intentar ejecutar esa supuesta instrucción.

En este caso la parte del autómata suprimida no contiene estados. Pero puede darse el caso de supresión de algún estado. Veámoslo.

En este mismo ejemplo, se puede suprimir el estado 3 si convenimos en que d (2, 0) = Æ quiere decir que ir a ningún estado es rechazar la palabra leída, que es el mismo convenio adoptado anteriormente. En este caso se llega a una situación de bloqueo desde un estado de aceptación.

 

Referencias: http://www.prismmodelchecker.org/lectures/pmc/17-omega%20regular.pdf
http://www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r26805.PDF
http://www.prismmodelchecker.org/lectures/pmc/17-omega%20regular.pdf
http://www.liafa.jussieu.fr/~colcombe/Talks/talk_msob_seattle_14.8.06.pdf

1 comentario:

  1. ¿Porqué no pueden basarse en el libro de texto? Esto es de notación confusa y de terminología también incoherente y no cumple en realidad con lo que se buscaba. Van 2 pts por el intento.

    ResponderEliminar