¿Es un CFG usando un lenguaje nulo decidible?

Question

Si tengo una gramática sin contexto G de tal manera que el lenguaje de G es nulo, ¿G es decidible?

Sé que la respuesta es sí, pero tengo problemas para probar esto. Mi primer pensamiento es decir que solo hay un estado, Q1, que es el estado de inicio y el estado de aceptación de una máquina de turing que es el equivalente de G. Esta máquina no aceptará ninguna entrada e inmediatamente se detendrá y aceptará porque ha llegado a una aceptación. estado. ¿Es esta una respuesta aceptable, o estoy aquí fuera?

EDITAR:

Como dijo Joel a continuación, el lenguaje que describí acepta todas las cuerdas. Para contrarrestar esto, propongo una segunda máquina, G '. G 'tiene 3 estados, el estado de inicio Q1, un Estado Q2 de Aceptar y un Estado de rechazo Q3. Q1 transición a Q3 en todos los símbolos en el alfabeto de G ', y también Q2. Q1 tiene una transición de Epsilon a Q2. Por lo tanto, si existen símbolos en la cadena que se alimenta a G ', G' rechazará. Si no hay símbolos, la única opción es llevar la transición de Epsilon al estado de aceptación. ¿Como suena eso?

EDITAR:

Se demostró que la solución anterior aceptaba el lenguaje l (g ') = {""}.

Answer 1

Como dijiste, la respuesta es sí. Una prueba general es el hecho de que dado un CFG GRAMO Puede fácilmente (bien) construir una TM simula derivaciones usando esa gramática. Sin embargo, está buscando una prueba corta para el lenguaje vacío. (El hecho de que tenga un CFG en este caso es irrelevante).

Estás en el camino correcto en que si puedes construir un TM que siempre se detenga por un lenguaje dado L, entonces L es decidible. Sin embargo, la máquina que describe realmente aceptará cada cadena, es decir, el lenguaje que consiste en cada cadena posible sobre el alfabeto. Esto se debe a que si el estado de inicio también es un estado de aceptación, entonces la máquina Turing aceptará inmediatamente cuando comience. No tiene que leer toda la cadena de entrada (o cualquier parte de ella) para aceptar.

Para definir un TM que no acepte nada, que el conjunto de estados de aceptación esté vacío. Para garantizar que su máquina siempre se detenga, su función de transición también puede estar vacía.