| 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.1 Lenguajes y Gramáticas

> > El lenguaje es un medio que se utiliza para comunicar ideas, emociones y deseos, el cual utiliza una serie de símbolos y reglas. Estos símbolos forman palabras, que a su vez se pueden expresar de manera audible o escrita y que se estructuran con base en reglas.

> > El lenguaje sirve para comunicar a las personas, pero, en esta época, se ha incrementado el uso de lenguajes para comunicarse con la computadora; el lenguaje que comunica a una persona con una computadora es el que se usará en este curso y se estudiará desde el punto de vista de la matemática lingüística, por lo que este se llama lenguaje formal. El lenguaje formal esta compuesto de palabras y reglas que estructuran estas palabras para formar sentencias.

> > La gramática es el conjunto de reglas para formar palabras y oraciones dentro de un lenguaje.

> > Para comenzar a formar palabras, primero debemos definir las partes que las componen. Una palabra esta formada de caracteres o cadenas de caracteres.

> > En matemática lingüística, las gramáticas se usan para formar palabras y sentencias, por lo que, para realizar el reconocimiento de las palabras, se describen las partes de que están formadas las palabras: por un carácter inicial α y un carácter final β. La representación de las palabras se hace por medio de cadenas de caracteres, cada carácter que forma a la cadena de caracteres se toma de el Alfabeto ∑.

> > Las gramáticas formales están compuestas de cuatro partes G = (S, N, T, P ), donde: S el símbolo inicial, N los símbolos no terminales, T los caracteres terminales y P el conjunto de producciones. Estas gramáticas fueron desarrolladas y clasificadas por Noam Chomsky.

> > Las formas de expresar las cadenas de caracteres, donde se considera un alfabeto ∑ {abecedario}, es como sigue:

> > A = bcd
> > B = d
> > λ = carácter vacío
> > Aλ = bcd λ = bcd

> > Una cadena de caracteres como una concatenación de símbolos (letras), es por ejemplo:

> > C = a e f g d a h i

> > La cadena de caracteres puede ser tan grande como sea necesario, por ejemplo:

> > AB = bcdd

> > La concatenación es la consecución de símbolos o caracteres. Las cadenas de caracteres tienen longitud, que se puede expresar como sigue:

> > |A| = 3
> > |B| = 1
> > | λ| = 0

> > El carácter vacío λ, también puede ser expresado por ε.

> > Las potencias de las cadenas de caracteres, se expresan de la siguiente manera:

> > A2 = AA = bcd bcd
> > A5 = AAAAA = bcd bcd bcd bcd bcd
> > A0 = λ

> > Las partes de las cadenas, si consideramos la siguiente cadena de caracteres, son:

> > C = acfgh

> > La primera parte es la cabeza y esta formada de los siguientes caracteres:

> > Cabeza (C) = {a, ac, acf, acfg, acfgh, λ}

> > La última parte es la cola, y esta formada de los caracteres que se expresan a continuación:

> > Cola (C) = {λ, h, gh, fgh, cfgh, acfgh}

> > La cabeza o la cola son propias si se cumple:

> > C = yz

> > Donde y y z no deben ser λ (el carácter vacío).

> > Cabeza (C) = a = yz

> > y = a y z = λ a λ

> > ó

> > y = λ y z = a λa

> > Cola (C) = yz

> > Donde y y z no deben ser caracteres vacíos.

> > La operación producto de las cadenas de caracteres, se expresa de la siguiente forma:

> > A·A

> > Si A ={a,b,cn} entonces la operación producto contiene las siguientes cadenas de caracteres:

> > A ·A = {aa, ab, acn, ba, bb, bcn, cna, cnb, cncn}

> > La concatenación de cadenas, se puede expresar por medio de la operación producto, como sigue:

> > A1 = {a, b, cn}
> > A2 = {aa, ab, acn, ba, bb, bcn, cna, cnb, cncn}
> > .
> > .
> > .
> > A∞ = {………}

> > La cerradura se expresa como A+ y no contiene el carácter vacío. Y se se representa por A+. La cerradura de Kleen, se expresa por medio de A* y por medio de la operación de productos:

> > A0, A1, A2, …, A∞

> > La cerradura de Kleen si contiene el carácter vacío, y se puede escribir como siguiente:

> > A* = {λ, A+}

> > Las formas de describir un lenguaje, se hace de tres maneras:

> > 1. Enumerando las palabras:

> > Lista 1 Lista2

> > While Árbol
> > Parser Mesa
> > Do Salón
> > Have Clase
> > It Alumno
> > He plumon
> > She

> > 2. Por medio de la teoría de conjuntos:

> > L1 {x | x = A2 donde A = cd}

> > X = {cdcd}

> > 3. Por medio de propiedades de las cadenas de caracteres.

> > L2 = {x | x = A3 donde A = cde AND λ E x}

> > Para describir completo un lenguaje se requiere el uso de gramáticas, el cual se expresa con la letra G.

> > La gramática formal contiene 4 partes. Y se expresa de la siguiente forma:

> > G (N, T, P, S)

> > Donde N = Son los símbolos no terminales
> > T = Son los símbolos terminales
> > S = Símbolo inicial
> > P = Las producciones

> > Si la gramática esta bien definida por si sola expresa un lenguaje.

> > Las operaciones con las cadenas de caracteres, para expresar palabras, son:

> > a+ ={a, aa, aaa, …}
> > a* = {λ, a, aa, aaa, …}
> > ?a = {a}

> > Otra forma de expresar a las palabras es por medio de los autómatas. Los números reales, se expresan por medio de una gramática y también por medio de un autómata, como se ve a continuación:

> > <signo> → + | -

> > N_r → <signo> <d> . <d>

> > De la gramática anterior se pueden obtener los siguientes números reales:

> > {2.0, 2, -2.1, +2.3, 3.666, …}

> > Y el autómata que representa a los números reales, es el siguiente:

> 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