Propiedades de modelos de verificación

Para esta semana la tarea es inventar una expresión regular y dibujar su NBA (Nondeterministic Büchi Automata).

Las expresiones regulares describen las combinaciones de caracteres en el texto, se puede definir como un conjunto de caracteres que forman un patrón, que representan a otro grupo de caracteres mayor, de forma que se pueda comparar el patrón con otros conjuntos de caracteres para ver las coincidencias. 

En la tabla siguiente se muestran algunos de los símbolos que se utilizan y lo que significa cada uno de ellos.

Entonces, como dijimos una expresión regular consiste en comprar un patrón con un texto para ver si el texto contiene dicho patrón.

Por ejemplo:

Patrón: Mi

- Miguel

- Camión

- Mimi

Patron: [mp] adre

-Madre

-Padre

Sintáxis y caracteres

El punto

Representa cualquier carácter, escribir un punto en un patrón significa que hay un carácter, cualquiera. Desde la A a la Z (mayúscula o minúscula), del 0 al 9, o algún otro símbolo.

Ejemplo:

pa.a coincide con pasa, pata, para, paja, etc. NO coincide: pasta ni paa.

Principio y fin de cadena

Si se quiere indicar que es el principio de la cadena o que es el final, se utiliza ^para inicio y $ para final.

Ejemplo:

^pájaros coincide con "pájaros amarillos", pero no con "bonitos pájaros"

$rosa coincide con "color rosa" 

Cuantificadores

Se utilizan para indicar que algún elemento del patrón se repetirá un número intedeterminado de veces, se utiliza "*" o "+". Usando "+" para decir que el elemento anterior aparece uno o más veces, y con "*" decimos que el elemento anterior aparece cero o más veces.

Por ejemplo:

"casa+" coincide con "casaa" "casaaa" "casaaaa", etc. 

"ab*c" coincide con "ac" "abc" "abbc" "abbbc", etc.

Si se quiere indicar un elemento que puede que esté (una vez) o puede que no esté se utiliza "?".

Se puede definir la cantidad de veces que se va a repetir, para esto se utilizan las llaves     "{ }".

Ejemplo:

abc{1,2} coincide con "abc" "abcc"

Mi expresión regular es la siguiente:

En esta expresión podemos ver que tiene un operador OR y uno AND, también cuenta con símbolos de los que observamos en la tabla anterior. El símbolo * significa que el carácter anterior se encuentra cero o más veces. 

El NBA correspondiente de esta expresión es el siguiente: