Câu đố biểu hiện chính quy

Question

Đây không phải là bài tập về nhà, mà là câu hỏi thi cũ. Tôi tò mò muốn xem câu trả lời.

Chúng tôi được cung cấp một bảng chữ cái S = {0,1,2,3,4,5,6,7,8,9, +}. Xác định ngôn ngữ L là tập hợp các chuỗi w từ bảng chữ cái này sao cho w có trong L nếu:

a) w là một số như 42 hoặc w là tổng số hữu hạn của số như 34 + 16 hoặc 34 + 2 + 10

và

b) số lượng đại diện bởi w là chia hết cho 3.

Viết một biểu thức chính quy (và một DFA) cho L.

Answer 1

này nên làm việc:

 
^(?:0|(?:(?:[369]|[147](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\ 
+)*[369]0*)*\+?(?:0\+)*[258])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]|0*(?: 
\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])|[ 
258](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0 
\+)*[147])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]|0*(?:\+?(?:0\+)*[369]0*) 
*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]))0*)+)(?:\+(?:0|(?:(? 
:[369]|[147](?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*) 
*\+?(?:0\+)*[258])*(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]|0*(?:\+?(?:0\+)* 
[369]0*)*\+?(?:0\+)*[147]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])|[258](?:0*(? 
:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147])* 
(?:0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[147]|0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+) 
*[258]0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*[258]))0*)+))*$ 

Nó hoạt động bằng cách có ba trạng thái đại diện cho tổng các chữ số cho đến nay modulo 3.Nó không cho phép các số 0 đứng đầu trên các số, cộng với các dấu hiệu ở đầu và cuối của chuỗi, cũng như hai dấu cộng liên tiếp.

Thế hệ của biểu thức chính quy và kiểm tra giường:

a = r'0*(?:\+?(?:0\+)*[369]0*)*\+?(?:0\+)*' 
b = r'a[147]' 
c = r'a[258]' 

r1 = '[369]|[147](?:bc)*(?:c|bb)|[258](?:cb)*(?:b|cc)' 
r2 = '(?:0|(?:(?:' + r1 + ')0*)+)' 
r3 = '^' + r2 + r'(?:\+' + r2 + ')*$' 
r = r3.replace('b', b).replace('c', c).replace('a', a) 

print r 

# Test on 10000 examples. 

import random, re 
random.seed(1) 
r = re.compile(r) 
for _ in range(10000): 
    x = ''.join(random.choice('') for j in range(random.randint(1,50))) 
    if re.search(r'(?:\+|^)(?:\+|0[0-9])|\+$', x): 
     valid = False 
    else: 
     valid = eval(x) % 3 == 0 
    result = re.match(r, x) is not None 
    if result != valid: 
     print 'Failed for ' + x 

Answer 2

Không phải là một giải pháp đầy đủ, chỉ là ý tưởng:

(B) một mình: Dấu "cộng" không quan trọng ở đây. abc + def cũng giống như abcdef vì lợi ích của quan hệ chia hết cho 3. Đối với trường hợp thứ hai, có một regexp đây: http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expression-to-determine-if-a-base-10-number-is-divisible-by-3

để kết hợp với yêu cầu (A), chúng ta có thể lấy dung dịch (B) và sửa đổi nó:

• đầu tiên nhân vật đọc phải 0..9 (không phải là một cộng)

• Input không phải kết thúc với một cộng, vì vậy: Duplicate mỗi tiểu bang (sẽ sử dụng S cho tình trạng ban đầu và S' để trùng lặp để phân biệt giữa chúng). Nếu chúng tôi đang ở trạng thái S và chúng tôi đọc một dấu cộng, chúng tôi sẽ chuyển sang S'.

• Khi đọc một số, chúng tôi sẽ chuyển đến trạng thái mới như thể chúng tôi đang ở trong S. Các trạng thái S' không thể chấp nhận (một) cộng khác.

• Ngoài ra, S' không phải là "chấp nhận trạng thái" ngay cả khi S là. (vì đầu vào không được kết thúc bằng dấu cộng).

Answer 3

Lưu ý rằng bộ nhớ của tôi về cú pháp DFA đã lỗi thời, vì vậy câu trả lời của tôi chắc chắn là một chút bị hỏng. Hy vọng rằng điều này mang lại cho bạn một ý tưởng chung. Tôi đã chọn bỏ qua hoàn toàn +. Như AmirW nói, abc + def và abcdef là như nhau cho mục đích chia.

Chấp nhận tình trạng là C.

A=1,4,7,BB,AC,CA 
B=2,5,8,AA,BC,CB 
C=0,3,6,9,AB,BA,CC 

Chú ý rằng ngôn ngữ trên sử dụng tất cả 9 cặp ABC có thể. Nó sẽ luôn luôn kết thúc tại A, B, hoặc C, và thực tế là mọi biến sử dụng được ghép nối có nghĩa là mỗi lần lặp lại xử lý sẽ rút ngắn chuỗi các biến.

Ví dụ:

1490 = AACC = BCC = BC = B (Fail) 
1491 = AACA = BCA = BA = C (Success)