Nociones Básicas Sobre Lenguajes Gramáticas Y Autómatas

Nociones básicas
sobre
Lenguajes
Gramáticas
y
Autómatas
Lenguajes y Gramáticas

En este capítulo vamos a sintetizar los conceptos básicos de gramáticas y lenguajes para la teoría de compiladores


Cadenas y Lenguajes


La noción más básica en la teoría de lenguajes es la tira o cadena de caracteres formada por la concatenación de caracteres.

La cadena mínima es la nula y ladenominaremos (.

Si tenemos un alfabeto o vocabulario { a, b}, algunas cadenas que se pueden formar con él serán:
( , a, b, ab, aa, ba, bb, aaa, aab, bba,……
El orden es importante, la cadena ab es diferente de la ba.

La concatenación de 2 cadenas es otra cadena. Ejemplo la concatenación de ab y aaa es otra cadena : abaaa.
Si una de las cadenas es la nula la concatenación de dos cadenasdeja inalterada la cadena : (.ab es la misma que ab.

La longitud de una cadena es el número de caracteres que la forman.

Potencia de una cadena es la cadena resultante de concatenar dicha cadena consigo misma tantas veces como indique el exponente:
Si x fuera la cadena abc entonces :
x0 = (., x1 = abc , x2= abcabc …….

Si se tienen dos conjuntos de cadenas de caracteres Ay B, se puede realizar su producto cartesiano AB, considerando los pares de cadenas del producto resultante como concatenados, es decir:
Si A = { a, b, cd } y B = { d, g}, entonces el conjunto producto es .
AB = { ad, ag, bd, bg, cdd, cdg}

Sabiendo realizar el producto de conjuntos de tiras, es fácil calcular potencias” de conjuntos, realizando el producto consigo mismo
A0= { (. } ; A1= A; A2= AA , etc.
Si A = { a, b}
A0= { (. }
A1= A = {a, b}
A2= AA ={aa, ab, ba, bb}
A3= AAA = { aaa, aab, aba, abb, baa, bab, bba, bbb}

Cierre transitivo de un conjunto A , que denominaremos A+ a la unión de sus potencias crecientes
A+ = A1 union A2 union A3 …… union An



Cierre transitivo y reflexivo de A , que denominaremos A* , a la union de suspotencias crecientes pero comenzando con la potencia cero
A* = A0 union A1 union A2 union A3 …… union An
es decir A* se forma añadiendo ( al A+


Lenguaje: su concepto


Un lenguaje está formado por los dos elementos siguientes:
• Un diccionario, que indica el significado de las palabras del lenguaje
• Un conjunto de reglas para describir las sentencias válidas del lenguaje. Esteconjunto forma la gramática del lenguaje.

Semántica : estudio del significado de las frases de un lenguaje y su interpretación. (el fondo).
Sintaxis: estudio de la estructura del lenguaje ( la forma).

Noción de lenguaje: un conjunto de tiras de caracteres

Una tira o sentencia es una secuencia ordenada de los símbolos

• Un símbolo es un elemento del vocabulario del lenguaje,que se emplea para formar las tiras o cadenas del mismo, que se llaman sentencias
• Un alfabeto o vocabulario es el conjunto de todos los símbolos que forman las sentencias del lenguaje

La operación básica para formar las cadenas del lenguaje es la concatenación de símbolos.



Noción de Gramática


Una gramática está formada por un cuarteto: ( N, T, P, S)
• N es elvocabulario No Terminal de símbolos introducidos por nosotros como elementos auxiliares para la definición de la gramática y no figuran en las sentencias del lenguaje.
• T es el vocabulario Terminal de símbolos que forman las sentencias del lenguaje.
• P es el conjunto de Reglas de Derivación de las cadenas, que tienen la forma tira1 ( tira2. Aplicando esta regla la tira1 se transforma en latira2.
• S es el elemento más importante del vocabulario N no terminal: el símbolo inicial o axioma, del que se derivan todas los demás aplicando las reglas P.

Ejemplo:
Sea la gramática G1:
N sólo tiene el símbolo no terminal S que es también el axioma
T tiene los símbolos terminales a y b
P consta de las reglas:
S ( ab
S ( aSb
Las tiras...