Cómo probar dos expresiones regulares son idénticos en forma matemática?

Question

Actualmente estoy trabajando en "expresión regular" ejercicios en el libro de texto ("Una Introducción a los Lenguajes Formales y Autómatas"), y el problema que estoy enfrentando es que la mayoría de las veces, mi solución es diferente a la del libro. Sin embargo, me doy cuenta de que podían expresar el mismo idioma, pero no pude encontrar una manera de demostrarlo. Me pregunto si hay una manera matemática (como la inducción) para demostrar que las dos expresiones regulares son realmente idénticas? Alguna sugerencia?

Gracias,

Answer 1

Eso es un problema extremadamente difícil. Se puede convertir la expresión regular para un DFA y minimizar, pero eso es PSPACE-completo...

Creo que los procedimientos para la determinación de equivalencia de las expresiones regulares es conocido por tomar al menos exponencial espacio y en el tiempo y en la mayoría de la doble exponencial de tiempo, pero puedo estar equivocado.

Answer 2

Más de un idioma $\Sigma$, dado un DFA con los estados $S = \{s_i\}$ (de los cuales, $A \subseteq S$ acepta) y la transición de la función de $\delta : S \times \Sigma \rightarrow S$ y el otro DFA con los estados $T = \{t_j\}$ (de los cuales, $B \subseteq T$ acepta) y la transición de la función de $\zeta : T \times \Sigma \rightarrow T$ puede "fácilmente" la construcción de un DFA con los estados $U = S \times T$ (producto Cartesiano) y la transición de la función de $\eta((s_i, t_j), \sigma) = (\delta(s_i, \sigma), \zeta(t_j, \sigma))$. A continuación, los dos DFAs son equivalentes iff los únicos estados accesible en este Cartesiano-producto DFA son un subconjunto de a $(A \times B) \cup ((S \setminus A) \times (T \setminus B))$ - es decir, es imposible llegar a un estado que está aceptando en uno de los primeros DFAs, pero no en el otro.

Una vez que hemos traducido las expresiones regulares para DFAs el tiempo, la complejidad va a ser $O(ST\Sigma)$.

Answer 3

Salomaa (1966) dio dos sistemas de prueba para demostrar que dos expresiones son equivalentes (iguales). Si no puedes acceder al enlace de arriba, hay una descripción en Kozen de notas de la conferencia. Kozen mismo dio otra completar la prueba del sistema.

Como se mencionó anteriormente, es PSPACE-completo si una expresión regular que genera todas las posibles cadenas (este es un caso particular de la expresión regular de equivalencia conocida como la universalidad). Esto no significa necesariamente que las pruebas son necesariamente largo, solo que son difíciles de encontrar.