đơn giản hóa cụm từ thông dụng

Question

Tôi đang thực hiện các bài tập về biểu thức chính quy và tôi thực sự không chắc chắn về cách thực hiện điều này.

Các biểu thức chính quy là:

((a*)(b*))*U(a*) 

Tôi thực sự xấu lúc này, nhưng tôi nghĩ rằng ((a*)(b*))* có thể được đơn giản hóa để (a U b)* Nhưng nếu điều này là đúng, so với trước U(a*) thực sự chỉ là một sự lặp lại, vì vậy Tôi hình toàn bộ biểu thức có thể được đơn giản hóa thành (a U b)*. Điều này có đúng không?

Chỉnh sửa: U là viết tắt của union

Answer 1

Bạn nói đúng. (a*b*)* có thể khớp với bất kỳ chuỗi ký tự nào và của b, vì vậy có thể (a U b)*, do đó chúng tương đương nhau. (a U b)* cắt nhau a* là a* vì vậy a* là một tập con của (a U b)*. Do đó, toàn bộ biểu thức có thể được đơn giản hóa thành (a U b)*.

Answer 2

gì ((a*)(b*))*U(a*) thực sự có nghĩa là (sao chép từ here)

NODE      EXPLANATION 
-------------------------------------------------------------------------------- 
    (      group and capture to \1 (0 or more times 
          (matching the most amount possible)): 
-------------------------------------------------------------------------------- 
    (      group and capture to \2: 
-------------------------------------------------------------------------------- 
     a*      'a' (0 or more times (matching the 
           most amount possible)) 
-------------------------------------------------------------------------------- 
    )      end of \2 
-------------------------------------------------------------------------------- 
    (      group and capture to \3: 
-------------------------------------------------------------------------------- 
     b*      'b' (0 or more times (matching the 
           most amount possible)) 
-------------------------------------------------------------------------------- 
    )      end of \3 
-------------------------------------------------------------------------------- 
)*      end of \1 (NOTE: because you are using a 
          quantifier on this capture, only the LAST 
          repetition of the captured pattern will be 
          stored in \1) 
-------------------------------------------------------------------------------- 
    U      'U' 
-------------------------------------------------------------------------------- 
    (      group and capture to \4: 
-------------------------------------------------------------------------------- 
    a*      'a' (0 or more times (matching the most 
          amount possible)) 
-------------------------------------------------------------------------------- 
)      end of \4 

biểu hiện này hiện phù hợp với tất cả các trình tự: abUa bU U aabbUaa aaUaa aaU Uaa bbU ababUaa aabbaabbUaa (nhìn vào here)

Không có cách nào để đơn giản hóa này, mà không cần loại bỏ chụp nhóm và thứ tự các chữ cái còn lại.

CHỈNH SỬA: Nếu U trong câu lệnh regex của bạn là viết tắt của "union", thì biểu thức này không hợp lệ. Không có cách nào để kết hợp bất cứ điều gì trong regex. Chỉ có OR và bạn cần sử dụng | (đường ống) cho điều đó. Nếu bạn muốn kết hợp ((a*)(b*))* và (a*) thì có thể nó sẽ là ((a*)(b*))*, nhưng vẫn khớp với bất kỳ thứ gì như abaab.

Tuy nhiên, việc chụp các nhóm trong câu lệnh regex của bạn là vô ích, vì vậy, chẳng hạn như [ab]* đủ để khớp với bất kỳ số nào của a và b.