상호 배타적 인 정규 표현식

Question

정규 표현식 목록이있는 경우 동일한 문자열에 대해 두 개의 정규 표현식이 모두 반환되지 않는다고 쉽게 판단 할 수 있습니까?

즉, 모든 문자열에 대해 목록의 최대 하나의 항목이 전체 문자열과 일치하는 경우에만 목록이 유효합니다.

확실하게 증명하기가 어려울 것 같습니다 (하지만 불가능할 수도 있습니다).하지만 주제에 대해 어떤 작업도 찾을 수없는 것 같습니다.

내가 물어 보는 이유는 정규 표현식을 받아들이는 토큰 화기에서 작업하고 있으며, 한 번에 하나의 토큰 만 입력 헤드와 일치 할 수 있도록하고 싶습니다.

Answer 1

순수 정규 표현식 (문맥 자유 또는 더 복잡한 언어를 인식하게하는 역 참조 또는 기타 기능 없음)으로 작업하는 경우 요청한 사항은 가능합니다. 할 수있는 일은 각 정규식을 DFA로 변환 한 다음 (일반 언어가 교차로 인해 닫히기 때문에) 두 언어의 교차점 인 을 인식하는 DFA에 결합합니다. 해당 DFA에 시작 상태에서 승인 상태까지의 경로가있는 경우 해당 문자열은 입력 regexen에서 모두 허용됩니다.

이 문제는 일반적인 regex-> DFA 알고리즘의 첫 번째 단계는 으로 정규식을 NFA로 변환 한 다음 NFA를 DFA로 변환한다는 것입니다. 하지만 마지막 단계 인 은 DFA 상태의 수가 급격히 늘어날 수 있으므로 매우 단순한 정규 표현식의 경우에만 이 가능합니다.

확장 정규식 구문으로 작업하는 경우 모든 내기가 꺼져 있습니다 : 문맥이없는 언어 은 교차로에서 닫히지 않으므로이 방법은 작동하지 않습니다.

Answer 2

Wkipedia article on regular expressions는 상태

주어진 두 정규식 서술 언어 본질적 같은지 여부를 결정하는 알고리즘을 작성할 수 있고, 최소 결정적 유한 상태 기계 각 발현을 감소 수행하며 결정들이 있는지 동형 (등가물)이다.

그러나 힌트는 없습니다.

물론 쉬운 방법은 많은 테스트를 실행하는 것입니다.하지만 우리는 모두 테스트의 단점을 증명 방법으로 알고 있습니다.

Answer 3

정규 표현식 만보고하면됩니다.

[0-9] 및 [0-9]+이있는 경우를 생각해보십시오. 그들은 분명히 다른 표현식이지만 문자열 "1"에 적용될 때 둘 다 동일한 결과를 생성합니다. 문자열 "11"에 적용되면 다른 결과가 생성됩니다.

요점은 정규 표현식이 정보가 충분하지 않다는 점입니다. 결과는 정규식과 대상 문자열에 따라 다릅니다.