Eeehhh

2.1.4 Gramáticas
Una gramática es un formalismo que genera un lenguaje, a su vez, dicho lenguaje puede
ser reconocido por un autómata. Las gramáticas proporcionan el conjunto de reglas quepermiten formar sentencias correctas.
Para el uso de gramáticas es conveniente establecer algunas reglas:
• Las letras mayúsculas A, B, C, D, E y S representan variables.
• Las letras minúsculasa, b, c, d, e y los dígitos representan terminales.
• Las letras griegas minúsculas α, β y γ denotan cadenas de variables y terminales.
Una gramática regular o gramática de estado finito genera unlenguaje regular, que está
hasta abajo de la jerarquía de Chomsky. Los lenguajes regulares tienen muchos usos en las
ciencias de la computación, pero no son lo suficientemente poderosos pararepresentar la
sintaxis de la mayoría de los lenguajes de programación.
Definición. Una gramática regular G es un cuarteto <VN,VT,P,S>, donde
VN es un alfabeto finito de símbolos no terminales(o variables);
VT es un alfabeto finito de símbolos terminales, tal que VT y VN son disjuntos;
P es un conjunto finito de producciones o reglas de la gramática G de la forma
αÆβ, y cadaproducción satisface:
|α| = 1 donde α pertenece a VN.
|β| es de la forma aB o a, con B en VN y a en VT.
S es un elemento no terminal distinguible de VN, llamado símbolo inicial.
Ejemplo. La siguientees una gramática regular:
S Æ bA
S Æ aB
A Æ abaS
B Æ babS
S Æ e
que también puede escribirse usando el símbolo | para agrupar producciones:
S Æ bA | aB | e
A Æ abaS
B Æ babS
dondeVN = {S, A, B };
VT = {a, b};
P = { S Æ bA, S Æ aB, A Æ abaS, B Æ babS, S Æ e} donde S, A y B ∈ VN;
S es el símbolo inicial.
El operador infijo Æ de las reglas de la gramática especifica quedonde hay una ocurrencia
de un símbolos no terminal, éste se puede reemplazar por el lado derecho de su regla
correspondiente.
Una derivación, denotada por el operador infijo ⇒, implica la...