| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I Introducción 1.1 Lenguajes y Gramáticas 1.2 Clasificación de las Gramáticas 1.3 Derivaciones y Reducciones

1.4 Árboles de sintaxis

1.5 Gramáticas Ambiguas

1.6 Formas de Backus-Naur (BNF)

UNIDAD II
UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

1.3 Derivaciones y Reducciones

> Para analizar el proceso de derivaciones y reducciones, hagamos el siguiente ejercicio: obtener por medio de derivaciones las palabras de los siguientes lenguajes.

> {0n 1n | n >= 0}

> Lo cual, también está representada por medio de la siguiente gramática.

> Go ({0, 1}, {s}, P, S)

> P = {S → 0S1, S → 2, S → 1}

> Solución:

> Se aplican las siguientes derivaciones:

> S 0S1 00S11 000S111 000111

> Por lo que se cumple el lenguaje, que es representado por las siguientes operaciones:

> 0111 = 01
> 0212 = 0011
> 0313 = 000111
> .
> .
> .
> 0∞1∞ = 0000… 1111….
> 0010 = λ

> L= {λ, 01, 0011, 000111, 00001111, ….}

> Otro ejemplo:

> Obtener el lenguaje que cumple con la siguiente condición:

> {ambn| m, n 0}

> G1= ( {a, b}, {S, A, B}, P, S)

> P= { S → AB,
> A → aA,
> A → λ,
> B → bB,
> B → λ}

> Solución:

> Se aplican las siguientes derivaciones:

> S AB aAB aaAB aabB aabbB aabb
> S AB aAB ab abB ab

> Mientras se cumplan las derivaciones no hay problema en las combinaciones que se hagan siempre y cuando la derivación sea de izquierda a derecha.

> L1= { λ, b, a, ab, abb, bb, aa, bbb, aaa, aabb, aaabbb, aabbb, aabb, …, abbb, …}

> G2 ( {a,b}, {S,Y}, P, S)

> P={ S → aS,
> S → a,
> S → b,
> S → bY,
> Y → b,
> Y → bY,
> S → λ}

> S aS abY abbY abbb
> S aS aa
> S aS ab
> S aS abY abb
> S aS a

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello