¿Puede haber "estados muertos" en una gramática libre de contexto?

18

¿Puede una gramática libre de contexto incluir "estados muertos" de un autómata, como

sol=({un,si,C},{UN,si,C},{UN→unsi,si→si,si→C,C→CC},UN)?

Las reglas de producción y se para siempre y nunca generarán una palabra. ¿Está esto permitido o DEBEN terminar las reglas de producción con un terminal en algún momento?si→CC→CC

context-free automata formal-grammars r3r57
fuente

Respuestas:

24

Las gramáticas libres de contexto pueden contener reglas improductivas . Esto se acepta porque cada CFG genera el mismo lenguaje que algunos CFG adecuados que no contienen reglas improductivas, ni producciones de cadenas vacías, ni ciclos; por lo tanto, es seguro asumir que un CFG es apropiado sin pérdida de generalidad.

ilke444
fuente
No del todo: los CFG adecuados deben cumplir dos requisitos más. Entonces reformularía esto.
reinierpost
@reinierpost: ¿Supongo que quiere decir que existen clases de CFG que prohíben reglas improductivas, pero que aún incluyen CFG no apropiados? Supongo que la reformulación podría ser tan simple como: "a menos que, por ejemplo, lo sean"
mhelvens
Quiero decir que no todos los CFG sin reglas improductivas son adecuados, lo que contradice su afirmación; pero la definición de CFG adecuados, al excluir explícitamente las reglas improductivas, deja en claro que esto es posible en CFG arbitrarios, así que eso es lo que escribiría.
reinierpost
Gracias por tus mejoras. Quise decir que hay subclases de CFG que no pueden contener tales reglas.
ilke444
¿Existe un CFG adecuado que no contenga reglas improductivas, ni producciones de cadenas vacías, ni ciclos que generen el mismo lenguaje que ({a}, {A}, {A-> epsilon}, A)? Me gusta la primera oración Tal vez la segunda oración debería ser "Esto se debe a que la definición de CFG permite cualquier cadena finita de terminales y no terminales como el lado izquierdo de una producción".
Theodore Norvell
3

Sí, por supuesto. Cada NFA se puede escribir como un CFG. Y construir un DFA con un 'estado muerto' (el término que me enseñaron, es 'hundirse') es trivial.

sol=({un},{UN},{UN→UN},UN)
{un}

ϵ

David
fuente