정규 표현식 동등성

Question

두 개의 임의의 정규 표현이 동등한 지 알아낼 수있는 방법이 있습니까? 나에게 복잡한 문제처럼 보이지만 DFA 단순화 메커니즘이나 무언가가있을 수 있습니까?

Answer 1

동등성을 테스트하려면 계산할 수 있습니다 최소 DFA 표현과 비교.

Answer 2

평등의 테스트 가능성은 정규 표현의 고전적인 특성 중 하나입니다. (NB는 PERL 정규 표현 또는 기술적으로 다른 것에 대해 이야기하고 있다면 이것은 유지되지 않습니다. 비 규제 초신성.)

RES를 일반화 된 유한 Automata A와 B로 돌린 다음 A의 수용 상태가 B의 시작 상태로 무효 전이를 갖고 B의 수용 상태가 반전되도록 새로운 자동 자동 AB를 구성합니다. 이것은 당신에게 B에 의해 받아 들여지는 모든 것을 제외하고 A가 받아 들인 모든 문자열을 받아들이는 오토 마톤을 제공합니다.

BA에 대해서도 똑같이하고 순수한 FA로 줄입니다. FA에 시작 상태에서 액세스 할 수있는 상태를 수락하지 않으면 빈 언어를 수락합니다. AB와 BA가 모두 비어 있음을 보여줄 수 있다면 A = B를 보여주었습니다.

Edit 헤, 나는 아무도 그곳에서 거대한 오류를 눈치 채지 못했다고 믿을 수 없다.

설명 된 Automata AB는 전반전이 A에 의해 받아 들여지고 후반부가 B에 의해 받아 들여지지 않는 문자열을 받아 들일 것입니다. 원한다 AB는 약간 까다로운 과정입니다. 나는 내 머리 꼭대기에서 그것을 생각할 수는 없지만, 그것이 잘 정의되어 있다는 것을 알고 있습니다 (그리고 아마도 A와 비 수락 상태를 대표하는 상태를 대표하는 상태를 만들 수 있습니다.

Answer 3

이것은 실제로 정규 표현의 의미에 달려 있습니다. 다른 포스터가 지적했듯이, 최소한의 DFA 로의 표현을 줄인다. 그러나 그것은 순수한 정규 표현에만 효과적이다.

현실 세계 Regex Libs (특히 등 리퍼니스)에서 사용 된 구성 중 일부는 규칙적이지 않은 언어를 표현할 수있는 힘을 제공하므로 DFA 알고리즘은 효과가 없습니다. 예를 들어 Regex : ([a-z]*) \1 공간으로 분리 된 동일한 단어의 이중 발생과 일치합니다 (a a 그리고 b b 하지만 b a ...도 아니다 a b). 이것은 유한 한 오토 마톤으로 전혀 인식 할 수 없습니다.

Answer 4

이 두 Perlmonks 스레드는이 질문에 대해 논의합니다 (특히 Blokhead의 응답을 읽으십시오).

• Regexps의 비교 만족도
• Regex 동등성 테스트