problema expresión regular

Question

¿Qué es la expresión regular para el idioma 0 ^m 1 ⁿ donde m + n es par?

Answer 1

Si se refiere a una cadena de 000...111... donde la longitud de la cadena es par, se puede utilizar ^(00)*(01)?(11)*$

Answer 2

Ok, por lo que debe tener en cuenta para cero los casos cuando hay pares e incluso cuando están. Esto requiere dos estados, uno para incluso ceros, uno de ceros impares. Entonces, para el caso raro de cero es necesario tener un 1 a continuación un número par de unos. Para el caso, incluso sólo tiene un número par de unos.

Es fácil escribir la DFA, pero no sé cómo trazar aquí, así que voy a aventurar una respuesta a la expresión regular:

(0 (00)* 1 (11)*) \/ (00)*(11)*