Regex (a?) * Không theo cấp số mũ?

Question

Tôi hiện đang xem xét các vấn đề về biểu thức chính quy có thể kết thúc chạy theo thời gian mũ khi khớp với một đầu vào nhất định, ví dụ: (a*)* và (a|a)* có khả năng hiển thị 'catastrophic backtracking' khi được so khớp với chuỗi aaaaab - 'trong chuỗi phù hợp, thời gian cần thiết để cố gắng để phù hợp với chuỗi tăng gấp đôi. Đây chỉ là trường hợp nếu động cơ sử dụng phương pháp backtracking/NFA để cố gắng thử tất cả các nhánh có thể trong cây trước khi bị lỗi, chẳng hạn như được sử dụng trong PCRE.

Câu hỏi của tôi là tại sao không phải là (a?)* dễ bị tấn công? Dựa trên sự hiểu biết của tôi về backtracking, những gì sẽ xảy ra trong chuỗi "aaaab" về cơ bản những gì sẽ xảy ra với (a|a)*. Nếu chúng ta xây dựng NFA bằng cách xây dựng Thomspson NFA tiêu chuẩn, chắc chắn cho mỗi quá trình chuyển đổi epsilon xảy ra, động cơ sẽ phải tiếp tục lấy chúng và quay ngược lại theo cách tương tự như trường hợp của hai người? Ví dụ: (bỏ qua một số bước và nơi @ thay thế epsilon):

"aaaa" khớp, nhưng không thể khớp 'b', không thành công (quay lại)
"aaaa @" khớp, 'b' fail (backtrack)
"aaa @ một" trận đấu, 'b' thất bại (backtrack)
"aaa @ một @" phù hợp, 'b' thất bại (backtrack)
...
"@ một @ a @ một @ a @ "kết quả phù hợp, 'b' không thành công (quay lại)

thử tất cả các kết hợp có thể có của epsilons và a, chắc chắn dẫn đến sự bùng nổ theo cấp số nhân của các tuyến đường?

Sẽ có ý nghĩa khi loại bỏ các chuyển tiếp epsilon khỏi NFA, nhưng tôi tin rằng điều này có tác dụng loại bỏ tất cả các yếu tố không xác định khỏi mẫu (a*)*. Điều này chắc chắn là dễ bị tổn thương, vì vậy tôi không hoàn toàn chắc chắn những gì đang xảy ra!

Cảm ơn bạn rất nhiều trước!

Chỉnh sửa: Nó đã được chỉ ra bởi Qtax rằng epsilons vẫn không thể có mặt khi NFA được truyền tải với backtracking truyền thống, nếu không (@)* sẽ cố gắng để phù hợp mãi mãi. Vì vậy, việc triển khai NFA nào có thể dẫn đến (a*)* và (a|a)* là theo cấp số nhân và (a?)* không phải như vậy? Đây là điểm mấu chốt của câu hỏi thực sự.

Answer 1

Ok, sau khi một số tính toán, tôi cuối cùng đã tìm ra được điều này là do sử dụng 'rào cản' trong việc triển khai NFA. Nói một cách đơn giản, các rào cản được đặt tại các điểm chiến lược trong NFA (chẳng hạn như trên nút ngay sau khi chuyển đổi 'a' trong cấu trúc NFA của *). Họ yêu cầu trận đấu đã diễn ra từ thời điểm trước đó rào cản đã bị đánh. Điều này ngăn không cho NFA xâm nhập vào một tình huống mà nó khớp với một số lượng vô hạn các epsilon và cho phép nó chấm dứt.

Nói cách khác, không thể đi từ một rào cản đến cùng một rào cản chỉ phù hợp với di chuyển điện tử - nếu điều này xảy ra, tuyến đường bị hủy và ngược lại xảy ra từ điểm trước đó. Điều này cũng có tác dụng phụ mà (a?) * Không dễ bị tổn thương khi nổ theo cấp số nhân, kể từ khi a? không thể khớp với null lần thứ hai.