Wyrażenie regularne dla ciągów bitów o parzystej liczbie 1s

Question

Niech L= { w in (0+1)* | w has even number of 1s}, tj. L jest zbiorem wszystkich ciągów bitów o parzystej liczbie 1s. Które z poniższych wyrażeń regularnych reprezentuje L?

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

Według mnie opcja D nigdy nie jest poprawna, ponieważ nie reprezentuje ciągu znaków o wartości zero 1s. Ale co z innymi opcjami? Jesteśmy zaniepokojeni liczbą 1s (parzystą lub nie), nie liczba zer nie ma znaczenia.

To jest odpowiednia opcja i dlaczego?

Answer 1

A jeśli fałsz. Nie jest dopasowywany przez 0110 (lub dowolny niepusty łańcuch zerowy)

B oznacza OK. Nie będę się tym przejmował, ponieważ marginesy strony są zbyt małe.

C nie zostanie dopasowane przez 010101010 (zero w środku nie jest dopasowany)

D jak powiedziałeś nie zostanie dopasowane przez 00 lub jakiegokolwiek innego # bez nich.

Tak tylko B

Answer 2

Poszukaj przykładów, które powinny pasować, ale nie. 0, 11011 i 1100 powinien cały mecz, ale każdy z nich zawiedzie jeden z tych czterech

Answer 3

C jest błędna, ponieważ nie pozwala na jakiekolwiek 0s pomiędzy drugim 1 z jednej grupy i pierwszy 1 z następnej grupy.

Answer 4

szybkie skrypt Pythona faktycznie wyeliminować wszelkie możliwości:

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) 

wyjście:

• usunięte c ponieważ nie na 0110
• usunięte d, ponieważ nie na 0110
• usunięto a, ponieważ pasowało do 1
• usunięto b, ponieważ pasowało do 10

Answer 5

Aby rozwiązać taki problem zalecana

1. Supply wzory kontrprzykład dla wszystkich "niepoprawnych" wyrażeniach regularnych. Będzie to ciąg w L, który nie jest dopasowany, lub dopasowany ciąg z L.

2. Aby udowodnić pozostały „prawidłowy” wzorca, należy odpowiedzieć na dwa pytania:

   • Czy każdy ciąg, który pasuje do wzorca należą do L? Można tego dokonać, tworząc właściwości, które powinien spełniać każdy z dopasowanych łańcuchów - na przykład liczba wystąpień jakiegoś znaku ...
   • Czy każdy ciąg znaków w L jest dopasowany przez wyrażenie regularne?Odbywa się to poprzez podzielenie L na łatwo podlegające analizie podklasy i pokazanie, że każdy z nich dopasowuje wzór na swój własny sposób.

(brak odpowiedzi ze względu na konkretne [praca domowa)].

Answer 6

Analizując wzór 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 

Jest dość oczywiste, że ten wzór będzie pasował tylko ciągi którzy 0,2,4, ... 1 „s.

Answer 7

Ta odpowiedź byłaby najlepsza dla tego języka

(0*10*10*)