Expression régulière pour des chaînes de bits avec le même nombre de 1s

Laisser L= { w in (0+1)* | w has even number of 1s}, c'est à dire L est l'ensemble de toutes les chaînes de bits avec le même nombre de 1s. Laquelle des expressions régulières ci-dessous représente L?

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

Selon l'option m' D n'est jamais correct car il ne représente pas la chaîne de bits à zéro 1s. Mais ce que sur les autres options? Nous sommes préoccupés par le nombre de 1s(ou même pas) et non pas le nombre de zéros n'a pas d'importance.

Alors laquelle est la bonne option, et pourquoi?

Notez que ce ne sont pas de la chaîne de recherche d'expressions régulières; ce sont des langues de correspondance des expressions régulières. Alors, n'oubliez pas de les ancrer lors de l'essai.

OriginalL'auteur Prasoon Saurav | 2010-04-24

  1. 9

    Un si faux. Elle n'est pas compensée par 0110 (ou les zéros seule chaîne non vide)

    B représente OK. Je ne vais pas la peine de le prouver ici depuis les marges de page sont trop petites.

    C n'obtenez pas compensée par 010101010 (zéro dans le moyen n'est pas assorti)

    D comme vous l'avez dit, n'obtient pas compensée par 00 ou tout autre # sans.

    Donc seulement B

    +1 pour l'Fermat de référence!
    Une ne correspondent 0*
    La chaîne "000" a un nombre pair de 1 à zéro (1s) mais les regex ne correspond pas. (Je suppose que je devrais avoir dit que la regex ne correspond pas 0+ que c'est la chaîne vide). --- J'ai fait ça parce que C'est important que les cas de coin qui n'avait pas été mis en place et je n'ai donc ici parce que je ne pense pas que ça valait le coup de sa propre réponse.
    Ah. OK, je t'ai eu... mis à Jour! Merci!

    OriginalL'auteur DVK

  2. 2

    De résoudre ce problème, vous devriez

    1. Approvisionnement en contre-exemple des modèles pour tous "incorrect" les expressions régulières. Ce sera soit une chaîne de caractères dans L qui n'est pas adapté, ou un correspondant de la chaîne de L.

    2. De prouver le reste "correct", vous devez répondre à deux questions:

      • Est-ce que chaque chaîne de caractères qui correspond à la forme appartenant à L? Cela peut être fait par l'élaboration de propriétés de chacune des chaînes mises en correspondance doit satisfaire, par exemple, le nombre d'occurrences de certains personnages...
      • Est chaque chaîne dans L compensée par la regexp? Ceci est fait en divisant L facilement analysable sous-classes, et de montrer que chacun d'entre eux correspond au modèle à sa façon.

    (Pas de réponses concrètes en raison de [devoirs]).

    OriginalL'auteur P Shved

  3. 1

    Examinant le schéma 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

    Son assez évident que ce modèle ne fait correspondre les chaînes qui ont 0,2,4,... 1'.

    OriginalL'auteur gnarf

  4. 0

    De chercher des exemples qui doit correspondre mais n'en ont pas. 0, 11011, et 1100 doivent tous correspondre, mais chacun d'échec de l'un de ces quatre

    OriginalL'auteur Michael Mrozek

  5. 0

    C est incorrecte car elle ne permet pas de 0s entre le deuxième 1 d'un groupe et le premier 1 le groupe suivant.

    OriginalL'auteur Ignacio Vazquez-Abrams

  6. 0

    Cette réponse qui serait le mieux pour cette langue

    (0*10*10*)
    Pourriez-vous nous donner quelques précisions? Une opinion n'est généralement pas suffisant.
    Votre expression ne correspond pas à 011011. Il faut lire: (0*10*10*)*, ce qui n'est pas mieux que 0*(10*10*)*

    OriginalL'auteur prabhat

  7. -1

    un script python rapide effectivement éliminé toutes les possibilités:

    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 sortie:

    • supprimé c parce qu'elle a échoué sur 0110
    • retiré d parce qu'il n'sur 0110
    • retiré parce qu'elle correspond à 1
    • supprimé b parce qu'elle correspond à 10
    Juste parce que vous n'avez pas démenti en B, ne signifie pas que vous avez prouvé B. bel effort, mais simplement fallacieux de la logique.
    oups, my bad. lorsque l'ancrage de l'expressions (plaçant chacune entre une ^ et $), la seule qui survit B. bien sûr, si vous souhaitez toujours avoir à le prouver...
    Je ne pense pas que les espaces dans les expressions régulières sont censés compter. Vous devez relancer avec les espaces ignorés.

    OriginalL'auteur Igor Serebryany