Expresión regular para cadenas de bits con número par de 1s

Question

Deje L= { w in (0+1)* | w has even number of 1s}, es decir, L es el conjunto de todas las cadenas de bits con número par de 1s. ¿Cuál de las siguientes expresiones regulares representa L?

A) (0 * 10 * 1) *
B) 0 * (10 * 10 *) *
C) 0 * (10 * 1) * 0 *
D) 0 * 1 (10 * 1) * 10 *

De acuerdo a mí la opción D nunca es correcta porque no representa la cadena de bits con cero 1s. Pero, ¿y las otras opciones? Nos preocupa la cantidad de 1s (pares o no), no importa la cantidad de ceros.

Entonces, ¿cuál es la opción correcta y por qué?

Answer 1

A si es falso. No se corresponde con 0110 (o cualquier cadena no vacía de ceros solamente)

B representa OK. No me molestaré en probarlo aquí ya que los márgenes de la página son demasiado pequeños.

C no quede igualada por 010.101.010 (cero en el medio no está adaptada)

D como usted ha dicho no llega acompañado de 00 o cualquier otro # sin queridos.

lo tanto, sólo B

Answer 2

buscar ejemplos que deben coincidir pero no lo hacen. 0, 11011, y debe 1100 todo el partido, pero cada uno de ellos falla por uno de los cuatro

Answer 3

C es incorrecta porque no permite ningún 0s entre 1 segundo de un grupo y la primera 1 del siguiente grupo.

Answer 4

un script en Python rápida en realidad elimina todas las posibilidades:

import re 

a = re.compile("(0*10*1)*") 
b = re.compile("0*(10*10*)*") 
c = re.compile("0*(10*1)* 0*") 
d = re.compile("0*1(10*1)* 10*") 

candidates = [('a',a),('b',b),('c',c),('d',d)] 
tests = ['0110', '1100', '0011', '11011'] 
for test in tests: 
    for candidate in candidates: 
     if not candidate[1].match(test): 
      candidates.remove(candidate) 
      print "removed %s because it failed on %s" % (candidate[0], test) 

ntests = ['1', '10', '01', '010', '10101'] 
for test in ntests: 
    for candidate in candidates: 
     if candidate[1].match(test): 
      candidates.remove(candidate) 
      print "removed %s because it matched on %s" % (candidate[0], test) 

la salida:

• quitado C, ya que falló en 0110
• eliminado d, ya que falló en 0110
• eliminado un porque coincidió en 1
• eliminado b porque coincidía en 10

Answer 5

Para resolver tal problema que debiera

1. suministro patrones contraejemplo a todas las expresiones regulares "incorrectas". Esta será una cadena en L que no se corresponde, o una cadena coincidente de L.

2. Para probar el patrón "correcto" restante, que debe responder a dos preguntas:

   • ¿Cada cadena que coincide con el patrón pertenecen a L? Esto se puede hacer ideando propiedades que cada cadena coincidente debería satisfacer, por ejemplo, el número de ocurrencias de algún carácter ...
   • ¿Se corresponden todas las cadenas en L con la expresión regular?Esto se hace dividiendo L en subclases fácilmente analizables, y mostrando que cada uno de ellos coincide con el patrón de su propia manera.

(No hay respuestas concretas debido a [tarea]).

Answer 6

Análisis del patrón de B:

^0*(10*10*)*$ 

^   # match beginning of string 
0*   # match zero or more '0' 
(   # start group 1 
10*  # match '1' followed by zero or more '0' 
10*  # match '1' followed by zero or more '0' 
)*   # end group 1 - match zero or more times 
$   # end of string 

Es bastante obvio que este patrón sólo coincidirá cadenas que tienen 0,2,4, ... 1 's.

Answer 7

Esta respuesta sería mejor para este lenguaje

(0*10*10*)