La Definición de Lenguajes Ordinarios

Question

He intentado y he quemado mi cerebro para entender la definición de Lenguas Ordinarias en Discrete Mathematics and its Applications(Rosen) sin alcanzar el objetivo de entender por qué la definición es así en este libro. En la página (789), estoy reformular la definición:

Tipo 3 gramáticas se definen como:

w1 --> w2 

que P1 es un no terminal, y W2 es de la forma:

w2 = aB 
w2 = a 

donde B es un no-terminal, y a es un terminal. Un caso especial es cuando W1 es el símbolo de inicio y W2 es lambda (la cadena vacía):

w1 = S 
S --> lambda 

Dos preguntas que no pude encontrar una respuesta para. Primero, ¿por qué no puede w2 tener el formato Ba. En segundo lugar, por qué lambda solo está permitido para el símbolo inicial solo. El libro afirma que, los idiomas regulares son equivalentes a la Automatización de estados finitos, y podemos ver fácilmente que podemos crear una FSA para ambos casos. Eché un vistazo a otros recursos, y estas restricciones no existen en estos recursos.

Answer 1

En primer lugar, ¿por qué no puede w2 ser de la forma Ba.

tomar las siguientes gramática con W como símbolo de inicio:

W -> lambda 
W -> aX 
X -> Wb 

genera {a ⁿ b ⁿ: natural n} que no es un lenguaje regular. Por lo tanto, esta restricción es esencial si desea generar solo idiomas regulares. Alternativamente, puede permitir w2 = Ba, pero prohíbe reglas de tipo w2 = aB - esto también da lenguajes regulares. Esa gramática construirá una palabra "hacia atrás".

Si permite ambos tipos de reglas, obtendrá una clase conocida como linear languages.

Segundo, porque lambda solo está permitido solo para el símbolo inicial.

Esto no es una restricción necesaria.

Puede eliminar todos los usos de lambda para símbolos no terminales: tome una regla W -> lambda, elimínela y reemplace todas las reglas U -> aw con U -> aw y U -> a. Obviamente, no puede eliminar el uso de lambda para símbolo de terminal (el idioma ya no producirá la palabra vacía).

Por lo tanto, cada gramática de tipo 3 que usa lambda en muchos lugares se puede "normalizar" a una gramática que utiliza lambda solo para el símbolo de inicio.