martes, 6 de noviembre de 2012

Expresión ω-regular

La tarea de esta semana consiste en:

"Inventen una expresión ω-regular con por lo menos dos símbolos y por lo menos dos operadores. Dibujen el NBA que le corresponde."

Que son las expresiones Regulares ?
          Una expresión regular, a menudo llamada también patrón, es una expresión que describe un
          conjunto de cadenas sin enumerar sus elementos.

Construcción de expresiones regulares
         Un cuantificador tras un carácter especifica la frecuencia con la que éste puede ocurrir. Los
         cuantificadores más comunes son +, ? y *:

          + => El signo más indica que el carácter que le precede debe aparecer al menos una vez. Por 
         ejemplo, "ho+la" describe el conjunto infinito holahoolahooolahoooola, etcétera.

          ? => El signo de interrogación indica que el carácter que le precede puede aparecer como mucho una
          vez. Por ejemplo, "ob?scuro" casa con oscuro y obscuro.

          * => El asterisco indica que el carácter que le precede puede aparecer cero, una, o más veces. Por
          ejemplo, "0*42" casa con 42042004200042, etcétera.

Esta es mi expresión: 

 y una vez definida, podemos dibujar su NBA (Nondeterministic Büchi Automaton):



Referencias