Emmanuel García: Tarea 10: Expresión w-regular y Autómata Buchi

lunes, 5 de noviembre de 2012

Para ésta tarea se pidió que se creara una expresión w-regular y a partir de ella creáramos un NBA.
Ésta expresión debía cumplir con 2 reglas:

Mi expresión w-regular es la siguiente:

$\sum = \left \{ A, B, C \right \}$

$AB^{*}(C^{+}B^{+} + C^{+}ACAB^{*})^{\omega}$

ó simplificada

$AB^{*}(C^{+} (B^{+} + ACAB^{*}) )^{\omega}$

El símbolo * indica que hay cero o más del elemento precedente. Por ejemplo ab*c puede significar, "ac", "abc", "abbc", "abbbc", etc.
El símbolo + indica que hay uno o más del elemento precedente. Por ejemplo ab+c puede ser: "abc", "abbc", "abbbc", etc, pero no "ac".
Igual que en expresiones booleanas, + es un OR, y los caracteres seguidos unos con otros es un AND.

El NBA ( Non-deterministic Buchi Automaton - Automata Buchi no determinista) es entonces el siguiente: