TERMINOLOGÍA, NOTACIÓN Y CONCEPTOS ELEMENTALES, ALFABETO, SÍMBOLOS, CADENA VACÍA, LENGUAJE, GRAMÁTICA

1.1.- TERMINOLOGÍA, NOTACIÓN Y CONCEPTOS ELEMENTALES, ALFABETO, SÍMBOLOS, CADENA VACÍA, LENGUAJE, GRAMÁTICA.

• 
  Alfabeto: Un alfabeto es un conjunto de símbolos finito y no vacío. Convencionalmente, utilizamos el símbolo [pic 1] para designar un alfabeto. Entre los alfabetos más comunes se incluyen los siguientes: 

1. 
   [pic 2]= {0,1}, el alfabeto binario
2. 
   [pic 3]= {a, b, ……z}, el conjunto de todas las letras minúsculas.
3. 
   El conjunto de todos los caracteres ASCII o el conjunto de todos los ASCII imprimibles.

• 
  Símbolos: Un símbolo es una representación tangible de algo abstracto, por lo tanto, es perceptible por medio de algunos de los sentidos, por ejemplo, una letra es un símbolo gráfico que representa un sonido concreto, un dígito es la representación de un valor numérico; los símbolos también pueden representar un concepto o una idea, como los que se emplean en arquitectura, electricidad y matemáticas. 
• 
  Cadena vacía: Es aquella cadena que presenta cero apariciones de símbolos. Esta cadena designada por [pic 4], es una cadena que puede construirse en cualquier alfabeto. 
• 
  Lenguaje: Es simplemente un conjunto de cadenas que incluyen símbolos de un alfabeto. Esta definición incluye lenguajes familiares, como los lenguajes naturales y los de programación de alto nivel, así como conjuntos de cadenas no relacionados. 
• 
  Gramática: que define los usos correctos de una lengua mediante preceptos. 

1.2.- LENGUAJES: PROPIEDADES DE UN ALFABETO CERRADO DE KLEENE, CERRADURA POSITIVA Y SU RELACIÓN CON EL LENGUAJE.
CERRADURA DE KLEENE 

Sea L un lenguaje sobre el alfabeto [pic 5], se define a L* como la cerradura de Kleene o cerradura estrella como la unión infinita de todas las potencias de L, incluyendo la potencia cero.

[pic 6]

Ejemplo:

Sea L1= {0,1}, entonces L1* = L10 [pic 7] L11 [pic 8] L12 [pic 9]…. 

= {[pic 10]}[pic 11]{0,1}[pic 12]{00,01,10,11}[pic 13]{000,001,010,011,…} [pic 14]

= {[pic 15],0,1,00,01,10,11,000,001,010,011,…}
Los lenguajes L1 = {[pic 16]} y L2 = [pic 17], son los únicos cuya cerradura de Kleene es finita, y dado que [pic 18]0 = {[pic 19]}, se cumple que [pic 20]* = {[pic 21]}, y por tanto, para ambos se tiene que: L1* = L2* = {[pic 22]}. También es interesante observar que aunque tengamos la igualdad de las cerraduras L1* = L2*, esto no significa que L1 y L2 tengan que ser iguales.
CERRADURA POSITIVA 

De manera similar, se define la cerradura positiva de L, como la unión infinita de todas las potencias de L a partir de uno.

[pic 23]

Ejemplo:

Sea L= {ab}, entonces L+ = {ab, abab, ababab, ababababab, ……}, mientras que L*= {[pic 24], ab, abab, ababab, ababababab, ……}.
PROPIEDADES DE LAS CERRADURAS

Para cualquier lenguaje L, se cumplen las siguientes propiedades:

L* = {[pic 25]} [pic 26] L+

L+ = L. L* = L* . L = L* . L+ = L+ . L*

(L+)+ = L+

(L*)* = (L+)* = (L*)+ = L*
Si [pic 27][pic 28] L, entonces se sigue necesariamente que: L+ = L*, mientras que si [pic 29] [pic 30] L, se cumple forzosamente que: L+ = L* - {[pic 31]}.
1.3.- OPERACIONES CON LENGUAJES: UNIÓN, CONCATENACIÓN, POTENCIACIÓN. 
CONCATENACIÓN: 

Sean L1 y L2 dos lenguajes, entonces L1 . L2 = {wx | w L1, x L2 } es el lenguaje concatenación de L1 con L2.
Ejemplo:

• 
  Sean los lenguajes L1 = {pátz, camé, yuré, cará, zitá} y L2 = {cuaro}, entonces la concatenación de L1 con L2 es L1. L2 = {pátzcuaro, camécuaro, yurécuaro, carácuaro, zitácuaro}.
• 
  Sean los lenguajes L1 = {01, 21} y L2 = {a, ba, ca}, entonces la concatenación de L1 con L2 es L1 . L2 ={01a, 01ba, 01ca, 21a, 21ba, 21ca}
• 
  Similarmente se puede obtener L2 . L1 ={a01, ba01, ca01, a21, ba21, ca21}

POTENCIA:

Sea L un lenguaje sobre el alfabeto [pic 32], entonces para cualquier n [pic 33] 0, se tiene que la enésima potencia de L se define recursivamente como sigue:
[pic 34] = {Ɛ} para n = 0

[pic 35] para n > 0

Ejemplo:

• 
  Sea L= { ab } entonces L0 = {[pic 36]}, L1 = { ab}
• 
  Sea L = {0,1} entonces L0 = {[pic 37]}, L1 = {0, 1}, L2 = {00, 01, 10, 11}, Etc.

UNIÓN:

Las demás operaciones de conjuntos se aplican igualmente a los lenguajes, es decir: si L1 y L2 son dos lenguajes cualesquiera, entonces L1 [pic 38] L2 , L1 [pic 39]L2 , L1 - L2 , L2 – L1 y L1 [pic 40]L2 también son lenguajes.
1.4 GRAMÁTICA GENERATIVA Y ÁRBOLES DE DERIVACIÓN: SÍMBOLOS TERMINALES, SÍMBOLOS NO TERMINALES, SÍMBOLOS INICIALES, REGLAS DE PRODUCCIÓN, DERIVACIÓN DE PALABRAS. 
GRAMATICA GENERATIVA:

Una gramática generativa es la cuarteta G= (N, [pic 41], S, P), donde:

[pic 42]es un alfabeto de símbolos terminales, 

N es la colección de símbolos no terminales, 

S es el símbolo inicial de una gramática (no terminal, S N) y 

P es la colección de reglas de sustitución, también llamadas producciones.
Ejemplo: G= (N, [pic 43], S, P), donde:

N= {S, A, B}

[pic 44]= {a, b}

P = {S⎝aB, S⎝bA, A⎝a, A⎝aS, A ⎝bAA, B⎝b, B⎝bS, B⎝aBB}

DERIVACIÓN DE PALABRAS:

El proceso de generar una cadena se llama “derivación”, donde la doble flecha [pic 45]significa genera o deriva; parte de un símbolo inicial representado por S. Los símbolos en minúsculas son los elementos del alfabeto [pic 46] y se les conoce como símbolos terminales, mientras que las letras mayúsculas se denominan símbolos no terminales (SNT), debido a que solamente aparecen durante el proceso de derivación, pero no pueden figurar en una cadena finalizada, estos son los símbolos que pueden ser reemplazados aplicando alguna de las reglas de sustitución o producciones.


Ejemplo: 

G= (N, [pic 47], S, P), donde:

N= {S, A, B, C}

[pic 48]= {a, b}

P = S[pic 49] aA

S[pic 50]aB

A[pic 51]aA

A[pic 52]bC

B[pic 53]bB

B[pic 54]bC

C[pic 55][pic 56] (por ser un estado de aceptación)
La secuencia de transiciones que genera la cadena w= aaab, es la siguiente:
S [pic 57] A [pic 58] A [pic 59] A[pic 60] C
La primer regla se interpreta como que la transición del estado S al estado A genera el símbolo a. La flecha [pic 61] expresa que S “es sustituido por” o “produce” la cadena Aa, de modo que puede utilizarse esta regla cuando se tiene al símbolo S en una cadena, el cual puede ser sustituido por la expresión que aparece a la derecha de la flecha.

Por lo tanto la cadena w= aaab se puede generar por medio de las reglas anteriores. De este modo si se parte del símbolo inicial S y se aplica la primer regla, se obtiene aA, y si luego se aplica en dos ocasiones la tercera regla, se obtiene aaaA, luego se emplea la cuarta regla para obtener aaabC y finalmente la última regla para terminar en aaab.

Este proceso se puede describir de manera compacta así:
S[pic 62]aA[pic 63]aaA[pic 64]aaaA[pic 65]aaabC[pic 66]aaab
ARBOL DE DERIVACIÓN:

Es un árbol que representa en forma gráfica la manera como una gramática dada genera a una cadena concreta y tiene las siguientes propiedades:

...