Equivalencia de idiomas regulares de decidir

Question

Dadas dos expresiones regulares $R$ $S$ sobre un alfabeto $\Sigma$ es posible decidir su equivalencia de la siguiente manera:

1. la construcción de dos autómatas finitos $M_R$ $M_S$ tal que $L(R) = L(M_R)$ $L(S) = L(M_S)$
2. construir un autómata $M$ tal que $L(M) = (L(M_R) - L(M_S)) \cup (L(M_S) - L(M_R))$
3. prueba de vacío de $L(M)$ utilizando un algoritmo de la accesibilidad de la en $M$

Me preguntaba si hay otra manera de determinar la equivalencia. Supongamos $M_R$ $M_S$ es el mínimo de la DFA (sin epsilon-mueve) tal que $L(R) = L(M_R)$$L(S) = L(M_S)$. Si tienen un número diferente de los estados, a continuación, $R$ $S$ no son equivalentes. De lo contrario vamos a $m$ el número de estados de los dos autómatas. Es cierto que $L(M_R) = L(M_S)$ fib $\{x \in L(M_R) : |x| \leq m +1 \} = \{x \in L(M_S) : |x| \leq m +1 \}$? Cómo probar que con la Myhill-Nerode teorema?

Answer 1

Aquí es un hormigón contraejemplo a la conjetura, ahora que estoy leyendo correctamente.

Deje $R=(a\lor b)^3\Big(a(a\lor b)^5\Big)^*$$S=(a\lor b)^3\Big(b(a\lor b)^5\Big)^*$. Estos tienen la $7$-estado DFAs cuyas transiciones tablas que se muestran a continuación; $s_0$ es el estado inicial, y $s_3$, se muestra en rojo, es el único aceptor de estado.

$$\begin{array}{r|cc} M_R&a&b\\ \hline s_0&s_1&s_1\\ s_1&s_2&s_2\\ s_2&\color{red}{s_3}&\color{red}{s_3}\\ \color{red}{s_3}&s_4&s_6\\ s_4&s_5&s_5\\ s_5&s_0&s_0\\ s_6&s_6&s_6 \end{array} \qquad\qquad \begin{array}{r|cc} M_S&a&b\\ \hline s_0&s_1&s_1\\ s_1&s_2&s_2\\ s_2&\color{red}{s_3}&\color{red}{s_3}\\ \color{red}{s_3}&s_6&s_4\\ s_4&s_5&s_5\\ s_5&s_0&s_0\\ s_6&s_6&s_6 \end{array}$$

Las ocho palabras de longitud $3$ son las únicas palabras de longitud en la mayoría de las $8$ $L(M_R)$ y en $L(M_S)$, pero los idiomas no son lo mismo: $a^9\in L(M_R)\setminus L(M_S)$.

El problema es que el mínimo de bucle redundante $s_3\to s_4\to s_5\to s_0\to s_1\to s_2\to s_3$ es demasiado largo y su punto de partida demasiado lejos desde el estado inicial, por lo que la diferencia en los dos idiomas no se presenta dentro de la primera $8$ transiciones.

Answer 2

Teorema Deje $\mathcal{A}$ $\mathcal{B}$ dos DFA del con $m$ a los estados y $n$ estados, respectivamente. A continuación, $\mathcal{L}(\mathcal{A}) = \mathcal{L}(\mathcal{B})$ fib $\{x \in \mathcal{L}(\mathcal{A}) : |x| < mn \} = \{x \in \mathcal{L}(\mathcal{B}) : |x| < mn \}$.

Prueba Nosotros probamos las dos direcciones de la doble implicación.

($\Rightarrow$) Trivial.

($\Leftarrow$) Se demuestra que el contrapositivo. Supongamos $\mathcal{L}(\mathcal{A}) \neq \mathcal{L}(\mathcal{B})$ y deje $w$ ser una palabra de longitud mínima tal que $w \not\in \mathcal{L}(\mathcal{A}) \cap \mathcal{L}(\mathcal{B}) = \mathcal{L}(\mathcal{A} \times \mathcal{B})$. Supongamos, por medio de la contradicción, que $|w| \geq mn$. Nos pusimos $X = \{\hat{\delta}_{\mathcal{A} \times \mathcal{B}}(q_0,x) : x \text{ prefix of } w\}$. Desde $|X| \geq mn+1$$|Q_{\mathcal{A}\times\mathcal{B}}| = mn$, no existen dos prefijos $u,u'$ $w$ tal que $\hat{\delta}_{\mathcal{A} \times \mathcal{B}}(q_0,u) = \hat{\delta}_{\mathcal{A} \times \mathcal{B}}(q_0,u')$. Podemos suponer w.l.o.g. que $u$ es un prefijo de $u'$. Por lo tanto, existen dos cadenas de $v,z$ tal que $uv = u'$ $u'z = w$ y, por tanto,$uvz = w$. Además desde $u \neq u'$, la cadena de $v$ es no trivial (es decir,$|v| \geq 1$). Ahora tenga en cuenta que $\hat{\delta}_{\mathcal{A} \times \mathcal{B}}(\hat{\delta}_{\mathcal{A} \times \mathcal{B}}(q_0,u),v) = \hat{\delta}_{\mathcal{A} \times \mathcal{B}}(q_0,u)$, es decir, el los personajes que componen la cadena de $v$ de plomo el autómata $\mathcal{A} \times \mathcal{B}$ a través de un bucle del estado $\hat{\delta}_{\mathcal{A} \times \mathcal{B}}(q_0,u)$ en sí mismo. Por lo tanto, la cadena de $uz$ es tal que $\hat{\delta}_{\mathcal{A} \times \mathcal{B}}(q_0,uz) = \hat{\delta}_{\mathcal{A} \times \mathcal{B}}(q_0,w)$ y $|uz|<|w|$. Esto contradice la minimality de $w$.

Answer 3

No he leído este documento, "la Prueba de la Equivalencia de los Regulares de Idiomas", por Almeida, Moreira, y Reis, pero el resumen suena muy prometedor:

Antimirov y Musgos presentan una reescritura sistema para decidir la equivalencia de dos (extended) de las expresiones regulares y argumentó que este método podría conducir a un mejor promedio-caso algoritmo que los que se basan en la comparación de el equivalente a un mínimo de DFAs. En este trabajo se presenta un enfoque funcional de una variante de este método, probar su exactitud y dar algunos experimental comparativo de los resultados. A pesar de ser un método de refutación, nuestros resultados preliminares llevar a la conclusión de que, efectivamente, este método es viable y es, casi siempre, más rápido que los métodos clásicos.