¿Son los lenguajes regulares necesariamente deterministas y libres de contexto?

Question

El problema original

Supongamos que M es un DCFL (Deterministic Context Free Language) y N es un lenguaje regular. Responde a las siguientes preguntas y justifica tus respuestas.

a) ¿Es M-N necesariamente libre de contexto?

b) ¿Es N-M necesariamente libre de contexto?

Mi intento

Dado que las DCFL son cerradas bajo complementación, si N es DCFL, entonces tanto a y b son verdaderas, pero ¿los lenguajes regulares son necesariamente DCFL?

Gracias de antemano.

Answer 1

Para responder a la pregunta titular, sí, todos los lenguajes regulares son lenguajes libres de contexto deterministas. Para cada lenguaje regular, hay un DFA, que podemos ver como un PDA que no utiliza su pila (al menos no para hacer nada útil). Claramente este PDA es determinista (es sólo un DFA).

Para las dos preguntas motivadoras que tenemos (sólo para hacer una explicación clara):

1. Si $A$ es regular, entonces también lo es $\overline{A}$ .
2. Si $B$ es libre de contexto determinista, entonces también lo es $\overline{B}$ .
3. Si $C$ es regular y $D$ es libre de contexto, entonces $C\cap D$ es libre de contexto (no estoy seguro de lo que ocurre si $D$ es un DCFL, si la intersección también lo es, pero al menos sigue siendo libre de contexto).

Entonces tenemos:

a) $M-N = M\cap \overline{N}$ por (1) $\overline{N}$ es regular, por (3) $M\cap \overline{N}$ es libre de contexto.

b) $N-M = N\cap\overline{M}$ por (2) $\overline{M}$ es libre de contexto (de hecho, determinista), entonces por (3) $N\cap\overline{M}$ es libre de contexto.

Así que no es necesario que los lenguajes regulares sean un subconjunto de los lenguajes libres de contexto deterministas para responder a las preguntas.

Answer 2

1) Cualquier lenguaje regular puede ser representado por un autómata finito determinista. Cualquier autómata finito (determinista) puede interpretarse como un autómata (determinista) pushdown en el que la pila permanece vacía. Por lo tanto, cualquier lenguaje regular es un DCFL.

2) Que las DCFL sean cerradas bajo complemento no es ciertamente suficiente para justificar que la diferencia de dos DCFL sea una DCFL. Puesto que $M-N = M\cap\overline{N}$ también necesitaría el cierre bajo la intersección. Desgraciadamente, Las DCFL no se cierran bajo la unión ni la intersección.

Sugerencia: demuestre que las (D)CFLs son cerradas bajo la intersección con un lenguaje regular considerando una PDA (determinista) para una DCFL, una DFA para algún lenguaje regular, y construyendo una PDA (determinista) para la intersección.