Una gramática que acepta el conjunto vacío por la regla S-> S

Question

Este fue un problema de tarea que sé que he respondido incorrectamente. Di:

S -> '' 

lo que significa que S se obtiene la cadena vacía. Sé que el conjunto vacío y la cadena vacía no son lo mismo. De acuerdo a mi profesor, la respuesta es:

S -> S 

Ahora, esa respuesta me parece extraño:

1. Nunca va a terminar.
2. No es tanto un lenguaje como la ausencia de uno.

entiendo desde un punto de vista estrictamente matemático, que no voy a llegar a ninguna parte con el número dos. Sin embargo, ¿es necesario que un idioma finalice? Tener un idioma que PUEDE durar para siempre suena bien, pero uno que nunca terminará suena lo suficientemente mal como para pensar que preguntaría si alguien sabe si es un requisito de idioma o no.

Answer 1

Desde el Formal Grammar Wikipedia page:

el lenguaje de G, denotado como L (G), se define como todas aquellas frases que se pueden derivar en un número finito de pasos de la símbolo de inicio S.

Comenzando con S, aplicando la regla de producción una vez para S da S. aplicando la regla dos veces da S. Por inducción, aplicando la regla de cualquier número finito todavía da S. Dado que no hay frases se pueden derivar en un número finito de pasos , el idioma está vacío, por lo que su profesor es correcto.

maneras alternativas para definir una gramática que acepta el conjunto vacío son L(G) = {} (la lengua está vacía) o P = {} (el conjunto de reglas de producción está vacío).