¿Qué es una expresión regular para cadenas de 0 y 1 con un número par de ceros y un número par de unos?Expresión regular para cadenas con un número par de ceros y unos
Tengo algo así como (1*01*01*)*(0*10*10*)*.
¿Se ve bien?
1100 está en el idioma, pero no coincide con su expresión. 10101 no está en el idioma, , pero su expresión coincide.
Sugiero comenzar por dibujar un DFA. Hay una máquina de 4 estados bastante obvia que reconoce este lenguaje. (¿Es posible hacerlo mejor?) La cadena vacía está en el idioma, por lo que el estado de inicio es un estado de aceptación. ¿Hay otros estados de aceptación? Para un estado S no aceptante, ¿hay un prefijo que lo lleve desde el inicio-> S? ¿Hay alguna manera de pasar de S a S sin tocar un estado de aceptación? ¿Hay un sufijo que lo lleve de S a un estado de aceptación?
Un contraejemplo para su expresión regular dada es 01010101.
Usted puede encontrar que escribir una expresión regular para este problema en particular
no va a ser posible (a menos que utilice algunas
extensiones que no son regulares a la lengua habitual de expresiones regulares).
Según lo mencionado por Jim Lewis a continuación, este debería ser un problema que se puede solucionar.
El conjunto de todas las cadenas de más de {0,1} con un número par de 0 y un número par de 1 es sin duda regular. Un DFA con cuatro estados debería ser suficiente. –
@Jim Lewis: Gracias, por una mayor consideración, tiene toda la razón. –
A menudo me he preguntado por qué las personas atacan cosas con las que luego descubren que no están de acuerdo. Tiendo a simplemente eliminarlo y reformular la respuesta. Me parece que el tachado no agrega ningún valor a la respuesta final, y nuestra "educación" se puede ver en la historia si alguien está interesado de todos modos. Es curioso ya que he visto a muchas personas hacerlo. – paxdiablo
Bueno, esta es probablemente la tarea, pero qué diablos:
^(00|11|(01|10)(00|11)*(01|10))*$
Editar: simplificado!
+1: Buen trabajo. Para que cualquiera quiera probar esto de forma interactiva, intente http://www.gskinner.com/RegExr/ – brainjam
@tloflin: ¿Usó JFLAP? Lo hice y me dio exactamente la misma respuesta :) – tiftik
@tiftik, jaja no, utilicé el Bloc de notas. Pero comencé con un DFSM y lo reduje, así que no estoy sorprendido. – tloflin
@tmp = $str =~ /0/g;
print scalar @tmp % 2 == 0 ? 'even' : 'odd';
Esta no es una expresión regular. Este es un programa – tiftik
Podría ser solo yo, pero esa pregunta no tiene sentido para mí por completo. Tal vez reformular? –
hey listen mate/.... solo estoy preguntando si lo que he hecho es correcto o no ... y si no quieres ayudar, entonces no ... – Kevinniceguy
"buen chico": no hay necesidad de una respuesta grosera a alguien que ** estaba ** tratando de ayudar señalando que su pregunta no estaba clara. (Y si eso es "bueno", odiaría conocer a "Kevinmeanguy" ...) –