DFA de 0 y 1 alternativos

La expresión regular puede ser cualquier cosa, desde un símbolo terminal, ∅, hasta la unión de dos expresiones regulares (R ₁ + R ₂ ), su concatenación (R ₁ R ₂ ) o su cierre R ₁ * también.

Ejemplos de expresiones regulares:

1. Expresión regular del conjunto de todas las strings de 0 y 1 que comienzan con dos ceros:

   00(0+1)*

2. Expresión regular del conjunto de todas las strings de 0 y 1 que tienen un número par de 0 seguido de un número impar de 1:

   (00)*1(11)*

3. Expresión regular del conjunto de todas las strings de 0 y 1 que contienen al menos un 0 y al menos dos 1:

   00*11(0+1)* + 0111*(0+1)*

Strings que serán aceptables por expresión regular con 0 y 1 alternativos –

1. ∈ (sin entrada, 0 y 1)
2. 010101….. (string que comienza con 0 seguido de 1 y así sucesivamente).
3. 101010….. (string que comienza con 1 seguido de 0 y así sucesivamente).

Ahora, una expresión regular para un conjunto de todas las strings que consisten en 0 y 1 alternos sería (01)* , donde puede aceptar ∈, 01, 0101, 010101…..etc pero esto restringe la string ya que siempre puede comenzar con 0 solamente.

Nuevamente, la expresión (10)* aceptará ∈, 10, 1010, 101010….etc pero esto también restringe la string ya que siempre puede comenzar con 1 solamente.

Entonces, introducimos 1(01)* y 0(10)* para cumplir con la brecha en los casos respectivos.

Mientras que 1(01)* rompe la restricción de strings que comienzan con 0, 0(10)* rompe lo mismo para strings que comienzan con 1.

Entonces, la expresión final es:

(01)* + (10)* + 0(10)* + 1(01)*

Figura: autómatas finitos de expresión regular para alternar 0 y 1