Page 74 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

74

Sí reiteradamente hacemos reescritura de tales producciones generará:

ASB

AASBB

AASBB
AA-AB-BB → S→ab

Aquí aplicamos la última regla que deja toda la expresión en símbolos terminales en consecuencia
ya no se puede seguir generando más cadenas. O sea, una vez que todo queda expresado en
términos del vocabulario terminal, no será posible ninguna otra generación.

Evaluando esta gramática es claro que el lenguaje que se genera será cadenas que puede
corresponder a la siguiente descripción general:

L(G) = { / N>0}
Ejemplo sea la gramática G = ({A, B, C, D}, {S, A, B}, S, P) donde p son las producciones:

1- S → ASB
2- A → B
3- AAA → AABB
4- S → D
5- A → AA
6- B → DCD
S BDDCD

Entonces:

A S B A A S B
AA- S- DCD  A-AA- AA – D – DCD

AAAB-- D --DCD esta sería una cadena resultante.

La pregunta obligada es qué orden uso las reglas, el caso es que usando las reglas de generación,
debe poder encontrarse un patrón general de las cadenas, para así expresar un lenguaje.

Ejemplo: sea la gramática G = (VN, VT, S, P) donde:

VN= {<NÚMERO>, <DIGITO>}

VT= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

S=<NÚMERO>

P= {<NUMERO>: =<DIGITO> <NUMERO>

<NÚMERO>: =<DIGITO>

<DIGITO>: =0, 1, 2, 3, 4, 5, 6, 7, 8 ,9

}