Page 75 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

75

Reescribiendo en atención a las reglas podría escribirse: 123045098765

Podría ser cualquier digito, dado que corresponde a los elegibles entre 0, 1,2…9 seguido por
más digito (esto es 0, 1, 2…9) ya que hay una recursión entre número y digito.
Cadenas:

Las cadenas que eventualmente se generan estarán dadas por variables minúsculas, o sea por los
correspondientes símbolos terminales. Con el fin de acercarnos más a las reglas de derivación, sin
entrar aún a la jerarquía de las gramáticas, que se corresponde con las jerarquías de lenguajes
expresada por Chomsky, agregamos los siguientes conceptos:

1- Lado las cadenas que tengan símbolos terminales y no terminales de manera indistinta,
se representan por letras griegas: Α Ρ Β Γ
2- La forma de derivación directa se expresa así: (Α  Β) ϵ P, donde P es el conjunto de
producciones o reglas.
3- Existe la siguiente forma de derivación.

Derivación directa:

Entendiendo que Γ Α Ρ es una cadena y sí existe una gramática G= (VT, VN, S, P) donde VT=
{A, B}, VN= {S}, en donde existe una relación de derivación directa del tipo: (Α  Β) ϵ P
Entonces se puede expresar la derivación directa así:
Γ Α Ρ  Γ Β Ρ y aquí tanto Γ Α Ρ, como, Γ Β Ρ son cadenas en relación de derivación directa.

Ejemplo: sea la gramática: G= (VT, VN, S, P) donde VT= {A, B}, VN= {S}, y el
conjunto de producciones es: S → AB Y S → ASB.

Sólo reemplazando la primera en la segunda regla tendríamos:

S AABB. Nótese que se fue directo a llegar a una cadena de símbolos terminales.
Acá, se logró llegar a los símbolos terminales de forma inmediata. Lo cierto es que, haciendo
reiteradas reescrituras, se obtiene un patrón general del lenguaje aceptado, tal como vimos atrás.

Producciones:

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

Aplicar las reglas 5, luego la 2 luego la 4 y por último la 6, o sea no hay un orden preestablecido,
a seguir. El detalle está en encontrar el patrón general del lenguaje generado, ensayando varias
producciones y reiterando algunas.