Introducción a la gramática en la teoría de la computación

Prerrequisito – Teoría de la Computación

Gramática:
Es un conjunto finito de reglas formales para generar oraciones sintácticamente correctas u oraciones significativas correctas.

Constituir de gramática:
la gramática se compone básicamente de dos elementos básicos:

1. Símbolos
   terminales: los símbolos terminales son aquellos que son los componentes de las oraciones generadas usando una gramática y se representan usando letras minúsculas como a, b, c, etc.
2. Símbolos
   no terminales: los símbolos no terminales son aquellos símbolos que participan en la generación de la oración pero no son el componente de la oración. Los símbolos no terminales también se denominan variables y símbolos auxiliares. Estos símbolos se representan con una letra mayúscula como A, B, C, etc.

Definición formal de gramática:
cualquier gramática se puede representar mediante 4 tuplas: <N, T, P, S>

• N – Conjunto finito no vacío de símbolos no terminales.
• T – Conjunto finito de símbolos terminales.
• P – Conjunto finito no vacío de reglas de producción.
• S – Símbolo de inicio (Símbolo desde donde comenzamos a producir nuestras oraciones o strings).

Reglas de producción:
una regla de producción o producción en informática es una regla de reescritura que especifica una sustitución de símbolo que se puede realizar de forma recursiva para generar nuevas secuencias de símbolos. Tiene la forma α-> β donde α es un símbolo no terminal que puede ser reemplazado por β que es una string de símbolos terminales o símbolos no terminales.

Ejemplo-1:
considere la gramática G1 = <N, T, P, S>

T = {a,b}    #Set of terminal symbols
P = {A->Aa,A->Ab,A->a,A->b,A-> }    #Set of all production rules

S = {A}    #Start Symbol

Como el símbolo de inicio es S, entonces podemos producir Aa, Ab, a,b, que pueden producir strings donde A puede ser reemplazada por las Strings mencionadas en las reglas de producción y, por lo tanto, esta gramática puede usarse para producir strings de la forma ( a+b)*.

Derivación de strings:

A->a    #using production rule 3
OR
A->Aa    #using production rule 1
Aa->ba    #using production rule 4
OR
A->Aa    #using production rule 1
Aa->AAa    #using production rule 1
AAa->bAa    #using production rule 4
bAa->ba    #using production rule 5

Ejemplo-2:
considere la gramática G2 = <N, T, P, S>

N = {A}   #Set of non-terminals Symbols
T = {a}    #Set of terminal symbols
P = {A->Aa, A->AAa, A->a, A->}    #Set of all production rules

S = {A}   #Start Symbol

Como el símbolo de inicio es S, entonces podemos producir Aa, AAa, a, que pueden producir strings donde A puede ser reemplazada por las Strings mencionadas en las reglas de producción y, por lo tanto, esta gramática puede usarse para producir strings de forma (a)* .

Derivación de strings:

A->a    #using production rule 3
OR
A->Aa    #using production rule 1
Aa->aa    #using production rule 3
OR
A->Aa    #using production rule 1
Aa->AAa    #using production rule 1
AAa->Aa    #using production rule 4
Aa->aa    #using production rule 3

Gramáticas equivalentes:
se dice que las gramáticas son equivalentes si producen el mismo idioma.

Diferentes tipos de gramáticas:
la gramática se puede dividir en base a:

• Tipo de reglas de producción
• Número de árboles de derivación
• Número de strings