Có thể đơn giản hóa biểu thức chính quy này thêm nữa không?

Question

Tôi đang làm việc trên một số bài tập về nhà cho các lớp học biên dịch của tôi và tôi có vấn đề sau đây:

Viết một biểu thức chính quy cho tất cả các chuỗi của một 's và b' s có chứa một số lẻ của số hoặc số lẻ là b (hoặc cả hai).

Sau rất nhiều công việc Bảng tôi đã đưa ra các giải pháp sau đây:

(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)* 

Tuy nhiên, là đây là đơn giản nhất mà tôi có thể lấy nó? Tôi đã xem xét việc xây dựng DFA cố gắng để giảm thiểu số lượng các tiểu bang ở đó để xem nếu nó sẽ giúp tôi đơn giản hóa nhưng tôi figured tôi sẽ yêu cầu rất kinh nghiệm regex trên SO đầu tiên.

Answer 1

Hãy Greg D's đề nghị bắt đầu với một (aa) *, và đi từ đó. Sepp2k gần như đã đúng, nhưng sự cân nhắc thực sự là bạn không quan tâm đến lá thư kia. Ý tôi là, khi bạn đang nhìn vào ràng buộc "số lẻ", bạn không quan tâm gì về những gì b nằm trong chuỗi của bạn. Như vậy, thanh b * 's bất cứ nơi nào bạn có thể :)

câu trả lời Sepp2k là gần đúng, nhưng điều này là đúng:

b* a b* (a b* a b*)* | a* b a* (b a* b a*)* 

Xây dựng, regex này hiểu ra tất cả các chuỗi với một số lẻ của một người (phần đầu tiên), và các chuỗi của OR với bất kỳ chuỗi nào chứa số lẻ b.

Answer 2

Tôi e rằng tôi không tin rằng regex của bạn được viết là chính xác. Hãy xem xét các chuỗi:

aba 

Chúng tôi có một vài lựa chọn cho trận đấu, nhưng thực tế là nó lẻ chiều dài có nghĩa là chúng ta phải phù hợp với một một duy nhất ở phía trước, vì vậy:

(a)(ba) 

Nhưng, thật đáng buồn , không thể cho nhóm chính thứ hai của bạn ở đó để phù hợp (ba).

Khi giao dịch với một ràng buộc như thế này, tôi thấy dễ dàng hơn để bắt đầu từ ràng buộc cốt lõi và đi từ đó. Trong trường hợp này, hạn chế của bạn là "lẻ", vì vậy hãy bắt đầu với

a(aa)* 

để buộc số lẻ a và chuyển từ đó. :)

Answer 3

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

b* a b* (a b* a b*)* | a* b a* (b a* b a*)* 

Answer 4

Tôi nghĩ bạn cần tiếp cận vấn đề một cách khác nhau.

Bạn đang cố gắng khớp với bất kỳ thứ gì không có số chẵn là cả số a và b.

Có thể sẽ dễ dàng hơn để bắt đầu với một cái gì đó khớp với số thậm chí số a và b. Tất cả những gì bạn phải làm vào thời điểm đó sẽ là thêm thứ gì đó vào cuối khớp với chuỗi nhỏ nhất mà bạn thực sự muốn khớp.