두 개의 일반 언어의 교차 검사

Question

두 언어에 공통된 문자열이 있는지 테스트하고 싶습니다. 이 두 언어는 아래에서 설명하는 정규 언어의 하위 집합에서 가져온 것으로, 두 언어 모두에 문자열이 있는지 여부 만 알아야 예제 문자열을 생성 할 수 있습니다.

언어가

/foo/**/bar/*.baz

** 경기는 0 개 이상의 문자 및 * 일치 /하지 않은 0 개 이상의 문자, 모두 같은 글로브와 같은 문자열로 지정 다른 문자는 리터럴입니다.

아이디어가 있으십니까?

덕분에, 마이크

편집 : 나는 잘 수행 할 것으로 보인다 뭔가를 구현하지만, 정확성 증명을 시도 아직

. 당신은 두 언어의 source 및 unit tests

Answer 1

빌드의 FA A 및 B를 참조하고 "교차로 FA"AnB을 구성 할 수 있습니다. AnB에 시작 상태에서 액세스 할 수있는 하나 이상의 수락 상태가있는 경우 두 언어에 모두있는 단어가 있습니다.

AnB을 작성하는 것은 까다로울 수 있지만,이를 다루는 FA 교과서가있을 것입니다. 내가 걸릴 접근 방식은 다음과 같습니다

• AnB의 상태는 각각 A 및 B의 상태의 직교 제품입니다. AnB의 상태는 (a, b)으로 표시됩니다. 여기에서 a은 상태가 A이고 b은 상태가 B입니다.
• 전이 (a, b) ->r (c, d) (의미가 기호에 r(c, d)-(a, b)에서 전이이다) a ->r c가 A로의 전환은 IFF에 존재하고 b ->r d는 B로의 전환이다.
• (a, b)은 A 및 B에 각각 a 및 b이 시작 상태 인 경우 시작 상태가 AnB입니다.
• (a, b)은 각각 해당 FA에서 수락 상태 인 경우 AnB의 수락 상태입니다.

이것은 내 머리 꼭대기에서 떨어져서 완전히 증명되지 않았습니다!

Answer 2

방금 ​​빠른 검색을 수행했으며이 문제는 결정할 수 있습니다 (일명 수행 할 수 있음). 그러나 좋은 알고리즘을 알지 못합니다. 하나는 용액이다 : (A)에 NFA 쌍이

1. 변환 모두 정규식과 B
2. A와 B의 교점을 나타내는 NFA, C를 작성
3. 이제 모든 문자열을 C에서 상태 수로 시도하고 C가 값을 받아들이는지 확인하십시오 (문자열이 길면 한 지점에서 상태를 반복해야하기 때문에).

나는 이것이 약간 어려울 수도 있음을 알고 있지만 이것이 내가 어떻게 알 수있는 방법이다.