As expressões regulares Equivalência

Question

Existe uma maneira de descobrir se duas expressões regulares arbitrárias são equivalentes? Se parece complexo problema para mim, mas pode haver algum mecanismo de simplificação DFA ou algo assim?

Answer 1

Para equivalência teste que você pode calcular os DFAs mínimos para as expressões e compará-los.

Answer 2

Testability da igualdade é uma das propriedades clássicas de expressões regulares. (N. B. Isto não se sustenta se você está realmente falando de expressões regulares Perl ou algum outro tecnicamente não regular superlinguagem.)

Transforme suas REs para autômatos finitos generalizados A e B, em seguida, construir um autômato nova A-B tal que os estados de aceitação de A têm transições nulos para os estados de início de B, e que os estados de aceitação de B são invertidos. Isto dá-lhe um autômato que aceita todas aquelas cordas aceite por um, exceto para todos aqueles aceito por B.

Faça o mesmo para B-A, e reduzir, tanto para FAs puros. Se um FA não tem aceitar estados acessíveis a partir de um estado inicial, em seguida, ele aceita a linguagem vazia. Se você pode mostrar que tanto A-B e B-A estão vazios, você mostrou que A = B.

Edit Heh, eu não posso acreditar que ninguém percebeu o erro gigantesco lá - um intencional, é claro :-P

O autômatos A-B como descrito aceitará aquelas cordas cuja primeira metade é aceite por A e cujo meio segundo não é aceite por B. Construção do desejado A-B é um processo um pouco mais complicado. Eu não posso pensar sobre isso em cima da minha cabeça, mas eu sei que é bem definido (e provavelmente envolve estados criando a representar os produtos de aceitar estados em A e estados não-aceitação em B).

Answer 3

Isso realmente depende do que você quer dizer com expressões regulares. Como os outros cartazes apontou, reduzindo as duas expressões para sua mínima DFA deve funcionar, mas ele só funciona para as expressões regulares puros.

Algumas das construções utilizadas nas libs regex mundo real (backreferences em particular) dar-lhes poder de expressar idiomas que não são regulares, então o algoritmo DFA não vai funcionar para eles. Por exemplo, a regex: ([a-z]*) \1 corresponde a uma dupla ocorrência da mesma palavra separadas por um espaço (a a e b b mas não b a nem a b). Isso não pode ser reconhecida por um autômato finito em tudo.

Answer 4

Estas duas PerlMonks tópicos discutir esta questão (especificamente, as respostas do blokhead lido):

• comparativa satisfiability de regexps
• Testing regex equivalência