TEMA 1.-INTRODUCCIÓN

INDICE

En este capíulo vamos a tratar algunos conceptos básicos que son necesarios a la hora de adquirir un conocimiento adecuado de los contenidos posteriores de las asignaturas

NOTACIÓN

MODELOS DE LA COMPUTACIÓN

GRAMÁTICAS GENERATIVAS

OPERACIONES CON LENGUAJES.

LENGUAJE GENERADO POR UNA GRAMÁTICA

JERARQUÍA DE CHOMSKY

EJEMPLOS QUÉ LENGUAJE GENERAN LAS SIGUIENTES GRAMÁTICAS?

NOTACIÓN
Las siguientes son algunas normas de notación que respetaremos en lo posible a lo largo del curso. En casos particulares en los que sea imposible seguirlas lo indicaremos explícitamente.
	ALFABETOS: A, B, C...
	CONJUNTO DE CADENAS SOBRE EL ALFABETO A: A^*
	CADENAS O PALABRAS AISLADAS, u, v, x (ltimas letras del alfabeto)
	LENGUAJES, L, M, N....
	LONGITUD DE UNA PALABRA u: \|u\|
	ENCADENAMIENTO DE DOS PALABRAS u y v: uv
	ITERACIÓN DE UNA CADENA i VECES: uⁱ
	CADENA VACÍA: e
	CADENA INVERSA DE u: u^-1
	A* SIN LA CADENA VACÍA: A⁺
		EJEMPLO.los siguientes son lenguajes cuyo contenido se debe de conocer sin problemas:
			L₁ ={a, b, e }, símbolos a, b y cadena vacía.
			L₂={aⁱbⁱ/i=0,1,2,...}, palabras formadas de una sucesión de a, seguida de la misma cantidad de símbolos de b.
			L₃={uu^-1/ u∈ A*} palabras formadas con símbolos del alfabeto A y que consisten de una palabra, seguida de la misma palabra escrita en sentido contrario.
			L₄={aⁿ²/n=1,2,3,...}, palabras que tienen un nmero de a que sea cuadrado perfecto, pero nunca vacía.

	GRAMÁTICA GENERATIVA
	Una gramáica independientemente del tipo que sea se define mediante una cuádrupla formada por (V,T, P, S) donde:
	V:es un alfabeto de símbolos no terminales o variables. Sus elementos se representan mediante letras mayúsculas.
	T:es un alfabeto de símbolos terminales. Sus elementos se representan mediante letras minsculas.
	P: es un conjunto de pares (a , b ) llamados reglas de producción donde (a , b )∈(V∪ T)* y a contiene al menos un síbolo de V. El par (a b ) se representa como ab
	S: es un elemento de V, llamado símbolo inicial o de partida.


		LENGUAJE GENERADO POR UNA GRAMÁTICA
		Dada la definición de la gramática con la cuádrupla especificada anteriormente podemos generar las distintas palabras que corresponde al lenguaje de esa gramática. Esta generación se hace mediante el siguiente PROCESO:
		Para generar las palabras del lenguaje comenzamos en el símbolo inicial S y vamos aplicando sucesivamente las reglas de producción (P) de la gramática especificada, de forma que vamos a ir obteniendo secuencias de símbolos terminales distintas en función de cual sea la regla aplicada en cada paso.
		Para establecer la idea de una forma rigurosa vemos las siguientes definiciones y ejemplos preliminares:
		DEFINICION:
		Dada una gramática G=(V, T, P,S) y dos palabras a , b ∈(V∪ T)^, decimos que b es derivable a partir de a en un paso (ab ) si y solo si existen palabras d₁,d₂∈(V∪ T) una producción sj tales que a =d₁s d_2, b=d₁jd₂.
		Ejemplo:
		Haciendo referencia a la gramática del ejemplo anterior, tenemos las siguientes derivaciones:
		E E + E (E) + E (E) + (E) (EE) + (E) (EE) + (E*E)

		DEFINICION:
		Dada una gramática G=(V, T, P,S) y dos palabras a , b ∈(V∪ T)^, decimos que b es derivable de a en un paso (a b)si y solo si existen una sucesión de palabras d₁, ..., d₂(n =1) tales que a =d ₁⇒ d₂⇒ ....... ⇒_n=b
		Ejemplo:
		En el caso anterior podemos decir que (EE) + (EE) es derivable a partir de E:
		E ⇒^(EE) + (E*E)
		DEFINICION:
		Se llama lenguaje generado por una gramática G =(V,T,P,S) al conjunto de cadenas formadas por símbolos terminales y que son derivables a partir del símbolo de partida S. Es decir L(G)={u ⇒ T^/ S ⇒^u}.
		EJEMPLO
		En el caso de la gramática de los ejemplos anteriores (EE)+(EE) no pertenece al lenguaje generado por G, ya que hay símbolos que no son terminales. Sin embargo (a+c)*(a+b) si pertenece a L(G), ya que se puede comprobar que es derivable a partir de E (símbolo de partida) y solo tiene símbolos terminales.
		NOTAS
		Si en una gramática comenzamos a hacer derivaciones a partir del símbolo original S, dicha derivación acabará cuando:
		Sólo queden símbolos terminales, en cuyo caso la palabra resultante pertenece a L(G).
		O cuando queden variables pero no se pueda aplicar ninguna regla de producción, en cuyo caso dicha derivación no puede llevar a ninguna palabra de L(G).
		En general, cuando estemos haciendo una derivación puede haber más de una regla de producción aplicable en cada momento.
		Si la gramática con la que estamos trabajando está clara eliminaremos el signo * de la derivación de varios pasos, es decir, en vez de escribir a⇒ *b escribiremos a⇒ .

EJEMPLOS QUÉ LENGUAJE GENERAN LAS SIGUIENTES GRAMï¿½ICAS ?
1.- Sea G={V,T,P,S} una gramática donde el símbolo de partida es S, V={S,A,B}, T={a, b}, las reglas de producción son
	S→ aB, S→bA	A→ aS, A→bAA,A→a	B→ aS,B →aBB,B→ b

2.- Sea G={V,T,P,S} una gramática donde el símbolo inicial es S , V={S,X,Y}, T={a, b,c} y las reglas de producción las siguientes:
	S→ abc, S→aXbc	Xb→ bX	Xc→ Ybcc
	bY→ Yb	aY→ aaX ,aY→aa

		JERARQUÍA DE CHOMSKY
		La Jerarquía de Chomsky es una clasificación de las gramáticas en función de la forma de éstas.
		GRAMÁTICA DE TIPO 0 O CON ESTRUCTURA DE FRASE: cualquier gramática, sin restricciones. Un ejemplo de este tipo es la gramática que define el lenguaje español.
		GRAMÁTICA DE TIPO 1 O DEPENDIENTES DEL CONTEXTO: si todas las producciones tienen la forma:
		a₁Aa₂→a₁βa₂ donde a₁a₂β ∈ (V∪ T)*, A ∈ V, β ≠ε, excepto posiblemente la regla S→ε, en cuyo caso S no aparece a la derecha de las reglas. (el precedente de la implicación tiene una variable A precedida o seguida por un símbolo del alfabeto) Un ejemplo de este tipo de gramática de tipo 1 es el siguiente: G=({S,X,Y} {a, b, c}, P, S ) donde las producciones P son S abc, aXbc Xb bX Xc Ybcc BY Yb AY aaX AY aa El lenguaje que genera L(G)={ aⁿbⁿcⁿ / n>=1}
		GRAMÁTICA DE TIPO 2 O LIBRES DE CONTEXTO: si cualquier producción tiene la forma;
		A→a , donde A ∈ V y a ∈ (V∪ T)* (el precedente de la implicación no posee símbolos terminales o del alfabeto) Un ejemplo de este tipo de gramï¿½ica es G=({S}, {a, b}, P,S) donde las producciones son S →aSb, S→ε donde se genera el L(G)={aⁱbⁱ / i>=0}
		GRAMÁTICA DE TIPO 3 O REGULARES: si toda la regla tiene la forma;
		A→ uB o A→ u , donde A,B ∈ V y u ∈ T* (el consecuente de la implicación posee una variable o símbolo no terminal precedida y seguida por un símbolo terminal o del alfabeto) Un ejemplo de este tipo3 de gramática es G=({S,B}, {a, b}, P,S) donde las producciones son S→ aS,S→ B B→ bB, B→ε donde se genera el L(G)={aⁱbⁱ /i,j>=0}

		DEFINICIÓN
		Un lenguaje se dice que es de un tipo i (i=0,1,2,3) si y solo si es generado por una gramática de tipo i. La clase o familia de lenguajes de tipo i se denota por L_i. Se puede demostrar que L₃⊆L₂⊆ L₁⊆ L₀.

OPERACIONES CON LENGUAJES.

DEFINICION: Llamamos lenguaje sobre un alfabeto Ã a cualquier subconjunto del universo de discurso: L ∈ Ã*.

El conjunto vacío es un lenguaje sobre cualquier alfabeto.

OPERACIONES ENTRE LENGUAJES Sean L₁, L₂, L₃ lenguajes sobre un mismo alfabeto Ã .

Unión
L1 ∪ L2 = {x ∈ Ã* / (x ∈ L₁) ∪ (x ∈ L₂)} Es una operación cerrada, la unión de lenguajes es un lenguaje.
Es asociativa: (L₁ ∪ L₂) ∪ L₃ = L₁ ∪ (L₂ ∪ L₃).
Tiene elemento neutro (el lenguaje vacío).
Es conmutativa: L₁ ∪ L₂ = L₂ ∪ L₁.
Es una proposición idempotente: L ∪ L = L.
Concatenación de lenguajes
L = L₁ . L₂ = {z ∈ L / ∃ x ∈ L₁ y ∃ y ∈ L₂ tal que z = x . y}
Es cerrada, asociativa y el elemento neutro es: { l }.
Teorema: Sean A, B, C ∈Ã *
A . (B &cup C) = (A . B) ∪ (A . C)
(A ∪ B) . C = (A . C) ∪ (B . C)
Es por tanto distributiva por derecha y por izquierda.
Potencia de un lenguaje
Sea L ∈Ã *. Definimos la potencia i-ésima de L como Lⁱ, resultado de concatenarse a si mismo i veces.
También definimos L¹ como L y L⁰ como {ε }.
Clausuras de un lenguaje
A la clausura de L la llamamos L* y está definida como la unión de todas las potencias de L (Cierre de Kleene):L*=∪^∞_i=0Lⁱ .
La clausura positiva, L⁺=∪^∞_i=1Lⁱ.
Teorema: i) L* = L⁺ si ε ∈ L
ii) L⁺ = L*-{ε}
Reflexión de L
L^-1 = {x / x^-1 ∈ L}
Teorema: i) (L^-1)^-1 = L
ii) (A . B)^-1 = B^-1 . A^-1
Homomorfismos
Esta operación se aplica sobre distintos alfabetos A y B de modo que f: A* →B* es homomorfismo si y sólo si f(x, y) = f(x).f(y) como consecuencia: f(ε)=ε f(a₁...a_n)=f(a₁)...f(a_n)