biểu hiện thường xuyên để xác định một số chuỗi nhị phân

Question

Làm thế nào bạn sẽ viết một biểu thức chính quy để xác định tất cả các chuỗi 0 và 1 của đó, như một số nhị phân, đại diện cho một số nguyên đó là bội số của 3.

Một số số nhị phân có giá trị sẽ be:

 
11 
110 
1001 
1100 
1111 

Answer 1

Sử dụng DFA here chúng tôi có thể tạo biểu thức chính quy theo cách sau, trong đó A, B, C thể hiện trạng thái của DFA.

A = 1B + 0A 
B = 1A + 0C 
C = 1C + 0B 

C = 1*0B // Eliminate recursion 

B = 1A + 0(1*0B) 
B = 01*0B + 1A 
B = (01*0)*1A // Eliminate recursion 

A = 1(01*0)*1A + 0A 
A = (1(01*0)*1 + 0)A 
A = (1(01*0)*1 + 0)* // Eliminate recursion 

Hệ quả là một PCRE regex như:

/^(1(01*0)*1|0)+$/ 

kiểm tra Perl/example:

use strict; 

for(qw(
11 
110 
1001 
1100 
1111 
0 
1 
10 
111 
)){ 
    print "$_ (", eval "0b$_", ") "; 
    print /^(1(01*0)*1|0)+$/? "matched": "didnt match"; 
    print "\n"; 
} 

Đầu ra:

11 (3) matched 
110 (6) matched 
1001 (9) matched 
1100 (12) matched 
1111 (15) matched 
0 (0) matched 
1 (1) didnt match 
10 (2) didnt match 
111 (7) didnt match 

Answer 2

Tôi không nghĩ là bạn muốn. Tôi không thể tin vào bất kỳ ngôn ngữ nào sử dụng một biểu thức chính quy có thể là cách tốt nhất để làm điều này.

Answer 3

Khi bạn chia một số cho ba, chỉ có ba phần còn lại có thể (0, 1 và 2). Những gì bạn đang nhắm đến là đảm bảo phần còn lại là 0, do đó là bội số của ba.

này có thể được thực hiện bởi một automaton với ba trạng thái:

• st0, bội số của 3 (0, 3, 6, 9, ....).
• ST1, bội số của 3 cộng 1 (1, 4, 7, 10, ...).
• ST2, bội số của 3 cộng 2 (2, 5, 8, 11, ...).

Bây giờ hãy suy nghĩ số bất kỳ số không âm (đó là tên miền của chúng tôi) và nhân nó với hai (tack một số không nhị phân vào cuối). Các hiệu ứng chuyển tiếp cho điều đó là:

ST0 -> ST0 (3n * 2 = 3 * 2n, still a multiple of three). 
ST1 -> ST2 ((3n+1) * 2 = 3*2n + 2, a multiple of three, plus 2). 
ST2 -> ST1 ((3n+2) * 2 = 3*2n + 4 = 3*(2n+1) + 1, a multiple of three, plus 1). 

Cũng nghĩ ra bất kỳ số không âm, nhân nó bởi hai sau đó thêm một (tack một nhị phân trên đến cùng). Quá trình chuyển đổi cho điều đó là:

ST0 -> ST1 (3n * 2 + 1 = 3*2n + 1, a multiple of three, plus 1). 
ST1 -> ST0 ((3n+1) * 2 + 1 = 3*2n + 2 + 1 = 3*(2n+1), a multiple of three). 
ST2 -> ST2 ((3n+2) * 2 + 1 = 3*2n + 4 + 1 = 3*(2n+1) + 2, a multiple of three, plus 2). 

Ý tưởng này là, cuối cùng, bạn cần kết thúc ở trạng thái ST0. Tuy nhiên, cho rằng có thể có một số lượng tùy ý các biểu thức con (và các biểu thức con phụ), nó không cho vay dễ dàng để giảm đến một biểu thức chính quy.

Những gì bạn phải làm là cho phép bất kỳ của chuỗi chuyển tiếp có thể nhận được từ st0 để st0 sau đó chỉ cần lặp lại chúng:

Những đun sôi xuống để hai chuỗi RE:

ST0 --> ST0          : 0+ 
    [0] 
ST0 --> ST1 (--> ST2 (--> ST2)* --> ST1)* --> ST0: 1(01*0)*1 
    [1]  ([0]  ([1] )* [0] )* [1] 

hoặc regex:

(0+|1(01*0)*1)+ 

Điều này ghi lại bội số của ba hoặc ít nhất mười lần đầu tiên tôi đã thử nghiệm.Bạn có thể thử bao nhiêu tùy thích, tất cả chúng sẽ hoạt động, đó là vẻ đẹp của phân tích toán học hơn là bằng chứng giai thoại.

Answer 4

Câu trả lời là (1(01*0)*10*)*, đó là người duy nhất cho đến nay mà làm việc cho 110011