Cụm từ thông dụng cho các chuỗi bit có số chẵn là 1s

Question

Gọi L= { w in (0+1)* | w has even number of 1s}, nghĩa là L là tập hợp tất cả các chuỗi bit có số chẵn là 1 giây. Cụm từ thông dụng nào dưới đây đại diện cho L?

Một) (0 * 10 * 1) *
B) 0 * (10 * 10 *) *
C) 0 * (10 * 1) * 0 *
D) 0 * 1 (10 * 1) * 10 *

Theo tùy chọn của tôi D không bao giờ chính xác vì nó không đại diện cho chuỗi bit có số không 1 giây. Nhưng còn lựa chọn nào khác? Chúng tôi lo ngại về số lượng 1s (dù có hay không) không phải số lượng số không quan trọng.

Sau đó, đó là tùy chọn chính xác và tại sao?

Answer 1

A nếu sai. Nó không được đối sánh bởi 0110 (hoặc bất kỳ chuỗi không rỗng nào chỉ 0 không)

B đại diện cho OK. Tôi sẽ không bận tâm chứng minh nó ở đây vì lề trang quá nhỏ.

C không được kết hợp bởi 010.101.010 (zero ở giữa không phù hợp)

D như bạn nói không được kết hợp bởi 00 hoặc bất kỳ kháC# không có người.

Vì vậy, chỉ B

Answer 2

Tìm các ví dụ phù hợp nhưng không phù hợp. 0, 11011 và 1100 tất cả đều phù hợp, nhưng mỗi trường hợp không thành công cho một trong bốn số

Answer 3

C không chính xác vì nó không cho phép bất kỳ 0 nào giữa nhóm thứ hai của nhóm thứ nhất và nhóm thứ nhất của nhóm tiếp theo.

Answer 4

một kịch bản python nhanh chóng thực sự loại bỏ tất cả các khả năng:

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) 

đầu ra:

• loại bỏ c vì nó không thành công trên 0110
• tháo d vì nó không thành công trên 0110
• đã xóa vì nó khớp với 1
• bị xóa b vì nó khớp với ngày 10

Answer 5

Để giải quyết một vấn đề như vậy, bạn nên

1. Cung cấp mô hình phản ví dụ cho tất cả regexps "không chính xác". Đây sẽ là một chuỗi trong số L không khớp hoặc chuỗi được đối sánh trong số L.

2. Để chứng minh "đúng" mẫu còn lại, bạn nên trả lời hai câu hỏi:

   • Liệu mỗi chuỗi phù hợp với mô hình thuộc về L? Điều này có thể được thực hiện bằng cách tạo ra các thuộc tính mà mỗi chuỗi phù hợp phải thỏa mãn - ví dụ, số lần xuất hiện của một số ký tự ...
   • Mọi chuỗi trong L có khớp với regexp không?Điều này được thực hiện bằng cách chia L thành các lớp con có thể phân tích dễ dàng và cho thấy mỗi lớp khớp với các mẫu theo cách riêng của nó.

(Không câu trả lời cụ thể do [bài tập]).

Answer 6

Kiểm tra mô hình 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 

của nó khá rõ ràng rằng mô hình này sẽ chỉ phù hợp với các chuỗi có 0,2,4, ... 1 's.

Answer 7

Câu trả lời này sẽ là tốt nhất cho ngôn ngữ này

(0*10*10*)