Es un lenguaje regular subconjunto de otro?

Question

Deje $L_1$ $L_2$ ser dos idiomas dado como expresiones regulares (en este tipo de tareas sucede a menudo que $L_1 \subseteq L_2$, pero viceversa es falso).

Hay una buena manera de demostrar que $L_1 \subseteq L_2$ ? Si sí, que usted piensa que podría explicar ese algoritmo?

Yo tenía una idea para la construcción de los lenguajes de expresiones regulares usando el teorema de Kleene y de demostrar que cada palabra de $L_1$ puede ser un prefijo o un sufijo de alguna palabra w $\in$ $L_2$, donde el resto de w puede ser omitido (es decir, en regex representación de la misma es bajo $^*$ señal).

OK, otra idea es utilizar la fuerza bruta - sólo se muestran paso a paso que cualquier palabra de $L_1$ es aceptado por la DFA correspondiente a $r_2$. Sin embargo, lo que si hay muchas palabras en $L(r_1)$?

Así que no creo que estas son buenas ideas.

Ejemplo: $$r_1 = (a+ab+bb)(a+b)^* \\ r_2 = aab^*$$ Obviamente $L(r_1) \text { is not a subset of } L(r_2)$, pero $L(r_2) \subseteq L(r_1)$.

Answer 1

La idea básica de un sistema automatizado de prueba es:

• convertir ambos idiomas para sus máquinas de estado finito determinista.
• Calcular el producto cruzado de las máquinas de estado finito con las transiciones $F: ([x,y],\sigma) => [F_x(x,\sigma), F_y(y,\sigma)]$
• Recopilar la lista de estados accesible, y su acceptivity de estado de ambos idiomas. Si hay cualquier
  • [rechazar, rechazar] los estados, entonces la unión de los dos idiomas no es el idioma universal (hay una palabra que ellos rechazan).
  • [rechazar, aceptar] los estados, la última no es un subconjunto de la anterior.
  • [aceptar, rechazar] los estados, a continuación, el ex no es un subconjunto de éste.
  • [aceptar, aceptar] los estados, los idiomas no son disjuntas.

Otras clases: dos idiomas son equivalentes si ambos son subconjuntos de uno a otro (sin embargo, hay otras pruebas de que); Un idioma es un subconjunto de otro idioma si es su subconjunto, pero no viceversa.