Gramática del sistema formal

n es un conjunto de símbolos no terminales.

Es un conjunto de símbolos terminales.

Para el símbolo de inicio, n.

p es un conjunto de reglas de producción, por ejemplo, donde (NT)*, es decir, no puede ser una cadena vacía.

NT=.

Algunos símbolos de inicio están representados por s

Por lo general, los símbolos no terminales están representados por letras inglesas mayúsculas y los símbolos terminales

Estos símbolos están representados por letras inglesas minúsculas letras.

Gramática (continuación)

Ejemplos

N={A, B,}, T={a, b}

Estudiantes :Ab, A Ba, B b, B Bb

Los idiomas que puede reconocer.

Ab Bab … Bbnab bbnab bn+1ab

b+ab

FSA correspondiente

Sintaxis (continuación)

Cuatro tipos de lenguajes y sus correspondientes gramáticas y máquinas

Tipo 0: Su gramática correspondiente es una gramática no restringida. Su regla de producto no tiene restricciones.

Tipo 1: Su gramática correspondiente es la gramática sensible al contexto. Sus reglas de generación están relacionadas con la parte superior e inferior, es decir, en la regla de generación 1 2 1 2, solo el lado izquierdo de la regla de generación debe ser 1 y el lado derecho debe ser 2, de modo que se derivará 1 2. La longitud de todos los símbolos en el lado derecho de la regla de generación debe ser mayor que .

Gramática (continuación)

Tipo 2: Su gramática correspondiente es una gramática sin texto. Sus reglas de generación no tienen contexto, pero solo hay un símbolo no terminal en el lado izquierdo de las reglas de generación.

El tercer tipo: su gramática correspondiente es la gramática regular. Sus reglas de generación restringen que puede haber como máximo un símbolo no terminal en los lados izquierdo y derecho de la regla de generación, y solo puede haber un símbolo terminal en el lado derecho de la regla de generación.