Departamento de Tecnologías de la Información

Tema 2. Fundamentos de la Teoría de Lenguajes Formales

Ciencias de la Computación e Inteligencia Artificial

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

Índice

2.1. Alfabeto

2.2. Palabra 2.3. Operaciones con palabras 2.4. Lenguajes 2.5. Operaciones con Lenguajes

2

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

Índice

2.1. Alfabeto

2.2. Palabra 2.3. Operaciones con palabras 2.4. Lenguajes 2.5. Operaciones con Lenguajes

3

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.1. Alfabeto

• Se llama alfabeto a un conjunto finito, no vacío, cuyos elementos se denominan “letras” o “símbolos”. Se definen los alfabetos por la enumeración de los símbolos que contiene. • Ejemplos : – A1={A, B, C, D, E, F , G, ..., Z} – A2={0,1} – A3={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} – A4={(, )}

4

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

Índice

2.1. Alfabeto

2.2. Palabra 2.3. Operaciones con palabras 2.4. Lenguajes 2.5. Operaciones con Lenguajes

5

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales •

2.2 Palabra

Se denomina palabra a toda secuencia finita de letras formada con los símbolos de un alfabeto. – Palabras sobre A1 : JOSE, ANA, RREDF, ABACZA – Palabras sobre A2 : 0 1

11001100

– Palabras sobre A3 : 12 9065

67890

– Palabras sobre A4 : ((())(

)()((

1111

Se usarán letras minúsculas para representar las palabras de un alfabeto :

•

x = JOSE

(sobre A1)

y = (())

(sobre A4)

z = 123456

(sobre A3)

Longitud de una palabra: número de símbolos (letras) que la componen: |x|=4 |y|=4 |z|=6

•

Se define la palabra vacía como aquella cuya longitud es cero. Se representa mediante la letra .

6

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales •

2.2 Palabra

Se define “universo del discurso” o “lenguaje universal” sobre el alfabeto ∑ W(∑) al conjunto de palabras que se pueden formar con las letras de un alfabeto, W(∑) es un conjunto infinito.

•

Ejemplo: un alfabeto con el menor número posible de letras (1). – A={a} – En este caso, W(A) = { , a, aa, aaa, aaaa, ...}, y contiene un número

infinito de elementos. •

La palabra vacía pertenece a todos los lenguajes universales de todos los alfabetos posibles.

7

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

Índice

2.1. Alfabeto

2.2. Palabra 2.3. Operaciones con palabras 2.4. Lenguajes 2.5. Operaciones con Lenguajes

8

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.3 Operaciones con palabras

• Concatenación de palabras Sean dos palabras x, y tales que x  W(∑), y  W(∑) Supongamos que x=A0A1...... Ai ,|x| = i ; y= B0B1...... Bj ,|y| = j Se llama concatenación de las palabras x e y (y se representa por xy) a otra palabra, z, obtenida poniendo las letras de x y a continuación

las de y : z= A0A1...... Ai B0B1...... Bj Se cumple que: |z|=|x|+|y|

9

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales •

2.3 Operaciones con palabras

propiedades de la concatenación : – Operación cerrada. Es decir, la concatenación de dos palabras de W(A) es otra palabra de W(A). Si x  W(A) e y  W(A), entonces xy  W(A). – Propiedad asociativa : x(yz)=(xy)z – Existencia de elemento neutro. El elemento neutro de esta operación es la palabra vacía , tanto por la derecha como por la izquierda. Siendo x una

palabra cualquiera, se cumple : x = x = x Al cumplir las tres propiedades anteriores, se trata de una operación con

estructura semigrupo con elemento neutro. – no cumple la propiedad conmutativa

10

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.3 Operaciones con palabras

• Potencia de una palabra Se denomina potencia i-ésima de una palabra a la concatenación consigo misma i veces. xi = xxx...xx |----------------| i

se cumplen las siguientes relaciones xi+1 = xix = xxi (i > 0) xixj = xi+j (i, j > 0) Para que ambas relaciones se cumplan también para i, j = 0, basta con definir x0 = , cualquiera que sea x. Ejemplo: x = ABCD, entonces x2 = xx = ABCDABCD x3 = xxx = ABCDABCDABCD

– la longitud de la potencia es |xi | = i *|x|

11

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.3 Operaciones con palabras

• Reflexión de palabras Sea x=A0A1...... An , se denomina palabra refleja o inversa de x, representado por x-1, a x-1 = x=AnAn-1...... A0 esta palabra está formada por las mismas letras, pero ordenadas de forma inversa.

12

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

Índice

2.1. Alfabeto

2.2. Palabra 2.3. Operaciones con palabras 2.4. Lenguajes 2.5. Operaciones con Lenguajes

13

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.4 Lenguajes

• Se denomina lenguaje sobre el alfabeto  a cualquier subconjunto del lenguaje universal W() L  W() • El conjunto vacío,  ,es un subconjunto de W(). Este lenguaje no debe confundirse con aquel que contiene únicamente a la palabra vacía. Para diferenciarlos hemos de darnos cuenta de la distinta

cardinalidad de ambos conjuntos, ya que

C() = 0 C({}) = 1 • Estos dos conjuntos serán lenguajes sobre cualquier alfabeto. El alfabeto en sí puede considerarse como un lenguaje : el formado por todas las posibles palabras de una letra.

14

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

Índice

2.1. Alfabeto

2.2. Palabra 2.3. Operaciones con palabras 2.4. Lenguajes 2.5. Operaciones con Lenguajes

15

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.5 Operaciones con Lenguajes

• Unión de lenguajes Consideremos dos lenguajes diferentes definidos sobre el mismo alfabeto L1  W() y L2  W()

Se denomina unión de ambos lenguajes al lenguaje formado por las palabras de ambos lenguajes : L1  L2={ x | x  L1 ó x  L2} • Propiedades de esta operación : – Operación cerrada. La unión de dos lenguajes definidos sobre el mismo alfabeto será otro lenguaje definido sobre ese alfabeto – Propiedad asociativa. (L1  L2)  L3 = L1  (L2  L3) – Existencia de elemento neutro. L   =   L = L – Propiedad conmutativa. Se verifica que L1  L2 = L2  L1 – Propiedad de idempotencia. Se verifica que L  L = L 16

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.5 Operaciones con Lenguajes

• Concatenación de lenguajes Consideremos dos lenguajes definidos sobre el mismo alfabeto, L1 y L2. La concatenación o producto de estos lenguajes es el lenguaje L1L2= { xy / x  L1 y x  L2} Las palabras de este lenguaje estarán formadas al concatenar cada una palabra del primero de los lenguajes con otra del segundo. – La concatenación de lenguajes con el lenguaje vacío es: L = L =  • Propiedades de esta operación : – Operación cerrada. La concatenación de lenguajes sobre el mismo alfabeto es otro lenguaje sobre ese alfabeto. – Propiedad asociativa. (L1 L2) L3 = L1 (L2 L3) – Elemento neutro. Cualquiera que sea el lenguaje considerado, el lenguaje de la palabra vacía cumple que {}L = L{} = L

17

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.5 Operaciones con Lenguajes

• Potencia de un lenguaje Se define la potencia i-ésima de un lenguaje a la operación de

concatenarlo consigo mismo i veces. Li = LLL ....L |------------| i

• Se cumplen las siguientes relaciones – Li+1 = LiL = LLi (i > 0)

– Li Lj = Li+j (i, j > 0) – Para que las relaciones se cumplan para i, j = 0, se define – L0 = {}, cualquiera que sea L 18

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.5 Operaciones con Lenguajes

• Clausura positiva de un lenguaje Se define la clausura positiva de un lenguaje L: 

L+ =  Li i=1

Lenguaje obtenido uniendo el lenguaje con todas sus potencias posibles excepto L0. Si L no contiene la palabra vacía, la clausura positiva tampoco. • Ya que cualquier alfabeto  es un lenguaje sobre él mismo (formado por las palabras de longitud 1), al aplicarle esta operación se observa que

+ = W() - {} 19

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.5 Operaciones con Lenguajes

• Cierre o Clausura de un lenguaje Se define el cierre o clausura de un lenguaje L como : 

L* =  Li i=0

Lenguaje obtenido uniendo el lenguaje con todas sus potencias posibles, incluso L0. Todas las clausuras contienen la palabra vacía.

• Se cumplen las siguientes relaciones:

– L* = L+  {} – L+ = L L* = L* L

(será imposible obtener la palabra vacía)

• Ya que el alfabeto  es un lenguaje sobre sí mismo,al aplicársele esta operación.

* = W() Se denominará * al lenguaje universal o “universo del discurso” sobre el

alfabeto  20

Teoría de Autómatas y Lenguajes Formales

Tema 2: Fundamentos de la Teoría de Lenguajes Formales

2.5 Operaciones con Lenguajes

• Reflexión de lenguajes Se llama lenguaje reflejo o inverso de L, representándose por

L-1

L-1 ={ x-1 / x  L } lenguaje que contiene las palabras inversas a las palabras de L

21

Teoría de Autómatas y Lenguajes Formales