Demostrar que el conjunto de los lenguajes regulares es un subconjunto propio del conjunto de los lenguajes libres de contexto

Question

Me cepillado (no tarea) en algún cálculo, la teoría y la encontré con este problema:

¿Cómo puede probar que el conjunto de los lenguajes regulares es un subconjunto propio del conjunto de los lenguajes libres de contexto.

Ahora sé un lenguaje es regular si y sólo si es aceptado por un autómata finito.

Y sé que es un lenguaje libre de contexto si y sólo si es aceptado por una de pila autómata.

Pero no estoy seguro de lo que es la solución.

Answer 1

Cualquier DFA es equivalente a una PDA que pasa a no introduzca nada en su pila, por lo tanto, todos los lenguajes regulares también están libres de contexto. Más formalmente:

A DFA se define como una 5-tupla (S, S, s0, d, F) que consiste en el alfabeto de entrada, conjunto de estados, estado de arranque, tabla de transición, y el conjunto de estados finales (aceptar).

A PDA se define como un 7-tupla, incluyendo todos los elementos de un DFA, además de dos parámetros adicionales: gamma (el alfabeto pila), y Z (el símbolo inicial pila). Una tabla de transición PDA es algo diferente de una tabla de transición de DFA: cada transición puede depender de tanto el símbolo de entrada y el símbolo actual de la pila, y las transiciones pueden empujar o pop de la pila.

Así que mediante la introducción de un alfabeto de pila ficticia que consiste en un solo símbolo, es trivial (aunque algo molesto y largo aliento para escribir!) Para mapear la tabla de transición de DFA (state, input) -> state a una tabla (state, input, stack) -> (state, stack) transición PDA equivalente.

Para completar la demostración de una relación adecuada subconjunto: existen lenguas que están libres de contexto, pero no es regular, por lo que los lenguajes regulares forman un subconjunto propio de los lenguajes libres de contexto. Ejemplo:. El lenguaje de cadenas que consta de paréntesis equilibrados