Kiểm tra giao điểm của hai ngôn ngữ thông thường

Question

Tôi muốn kiểm tra xem hai ngôn ngữ có một chuỗi chung hay không. Cả hai ngôn ngữ này là từ một tập hợp con các ngôn ngữ thông thường được mô tả dưới đây và tôi chỉ cần biết liệu có tồn tại một chuỗi trong cả hai ngôn ngữ, không tạo ra một chuỗi ví dụ hay không.

Ngôn ngữ được xác định bởi một chuỗi glob giống như

/foo/**/bar/*.baz

nơi ** trận 0 hoặc các ký tự hơn, và * trận đấu không hoặc nhiều ký tự mà không phải là /, và tất cả các ký tự khác là chữ.

Bất kỳ ý tưởng nào?

cảm ơn, mike

EDIT:

tôi thực hiện một cái gì đó mà dường như thực hiện tốt, nhưng vẫn chưa thử một bằng chứng đúng đắn. Bạn có thể xem source và unit tests

Answer 1

xây dựng chi hội A và B cho cả hai ngôn ngữ, và xây dựng các "ngã tư FA" AnB. Nếu AnB có ít nhất một trạng thái chấp nhận được từ trạng thái bắt đầu, thì có một từ có cả hai ngôn ngữ.

Xây dựng AnB có thể phức tạp, nhưng tôi chắc chắn có sách giáo khoa FA bao gồm nó. Cách tiếp cận tôi sẽ thực hiện là:

• Các trạng thái của AnB là sản phẩm Cartesian của các bang A và B tương ứng. Tiểu bang ở số AnB được viết (a, b) trong đó a là tiểu bang ở A và b là tiểu bang ở số B.
• Một chuyển (a, b) ->r (c, d) (có nghĩa là, có một sự chuyển tiếp (a, b)-(c, d) vào biểu tượng r) tồn tại khi và chỉ khi a ->r c là một sự chuyển tiếp trong A, và b ->r d là một sự chuyển tiếp trong B.
• (a, b) là trạng thái bắt đầu ở AnB iff a và b là các trạng thái bắt đầu lần lượt là A và B.
• (a, b) là trạng thái chấp nhận trong AnB iff từng là trạng thái chấp nhận trong FA tương ứng của nó.

Đây là tất cả ngoài đỉnh đầu của tôi và do đó hoàn toàn chưa được chứng minh!

Answer 2

Tôi vừa tìm kiếm nhanh và vấn đề này là có thể giải quyết được (có thể được thực hiện), nhưng tôi không biết bất kỳ thuật toán tốt nào để thực hiện. Một là giải pháp là:

1. Chuyển đổi cả thường xuyên biểu để NFAs A và B
2. Tạo một NFA, C, đại diện cho giao điểm của A và B.
3. Bây giờ hãy thử mỗi chuỗi từ 0 đến số trạng thái trong C và xem nếu C chấp nhận nó (vì nếu chuỗi dài hơn, nó phải lặp lại trạng thái tại một thời điểm).

Tôi biết điều này có thể hơi khó thực hiện nhưng đây chỉ là cách tôi biết cách thực hiện.