Teoría de Autómatas y Lenguajes Formales Capítulo 2: “Lenguajes Formales” Holger Billhardt [email protected]

Sumario:


Capítulo 2: “Lenguajes Formales” 1. 2.

Concepto de Lenguaje Formal Operaciones sobre Lenguajes Formales (u otros conjuntos)

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

2

1

Sumario: Capítulo 2: “Lenguajes Formales”




1. 2.

Concepto de Lenguaje Formal Operaciones sobre Lenguajes Formales (u otros conjuntos)

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

3

Concepto de Lenguaje Formal


¿Qué es un lenguaje?






Informalmente: un lenguaje es un conjunto de palabras o sentencias formadas sobre un alfabeto

Pasaremos a definirlo de manera formal.

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

4

2

Concepto de Lenguaje Formal


Alfabeto: 

Definición (Alfabeto):


Conjunto finito, no vacío, de elementos.

Generalmente usaremos Σ para especificar alfabetos y los elementos los denominaremos “letras” o “símbolos”.


Ejemplos:        

los alfabetos español, inglés, o alemán Σ1={0,...,9}, 0∈Σ1 Σ2={x | x es un símbolo del código ASCII} Σ3={(, )} Σ4={1, A, 2, B} Σ5={a, b, c, d} Σ6={} Σ7=ℵ

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

5

Concepto de Lenguaje Formal


Palabras: 

Definición (Palabra):


Sea un alfabeto Σ. Una palabra sobre Σ es una secuencia finita de las letras de ese alfabeto.

La secuencia vacía representa la palabra vacía y la anotamos con λ.


Ejemplos: sobre Σ5 ={a,b,c,d}: λ, a, b, c, d, abc, aab, dcba, ... sobre Σ1 ={0,...,9}: λ, 0, 0000, 010, 9980, ... sobre Σ3 ={(,)} λ, (, ), (), (()()), )())), ...

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

6

3

Concepto de Lenguaje Formal


Palabras: 

Definición (Longitud de una palabra):


Se llama longitud de una palabra x, y se representa por |x|, al número de símbolos que la componen.




Ejemplos: sobre Σ5 ={a,b,c,d}: |λ|=0, |a|=1, |abc|=3

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

7

Concepto de Lenguaje Formal Operaciones con palabras:




Definición (Concatenación):


Sean dos palabras x e y definidas sobre el alfabeto Σ. La concatenación de x e y, denominada “xy”, es una palabra que contiene todos los símbolos (de derecha a izquierda) de x seguidos de los símbolos de y (de derecha a izquierda). Sean x=A1A2...An e y=B1B2...Bm con Ai, Bi ∈ Σ:




⇒ xy= A1A2...AnB1B2...Bm Ejemplos: x =abc, y =da, definidos sobre Σ={a,b,c,d} xy=abcda ; |xy|=|x|+|y|=5

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

8

4

Concepto de Lenguaje Formal


Operaciones con palabras: 

Propiedades de la concatenación:





Operación cerrada: sí Si x e y están definidos sobre Σ, entonces xy está definido sobre Σ. asociativa: sí x(yz)=(xy)z




Elemento nulo: λ xλ=λx=x




Conmutatividad: no xy≠yx

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

9

Concepto de Lenguaje Formal


Operaciones con palabras: 

Definición (Potencia):


Sea i un número natural, y x una palabra. La potencia i-ésima de x, denominada xi, es la operación que consiste en concatenarla consigo misma i veces.




Ejemplos: x =abc ⇒ x1=abc x2=abcabc x3=abcabcabc

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

10

5

Concepto de Lenguaje Formal


Operaciones con palabras: 

Propiedades de la potencia: ∀ i, j > 0
xi+1=xxi=xix
xixj=xi+j 






Se define x0=λ (palabra vacía): Si i=0 ⇒ x0+1=x1=x=xλ=xx0=λx=x0x Si i,j=0 ⇒ xixj=x0x0=λλ=λ=x0=x0+0 Nota: λλ=λ; λx=x; λλxλ=x

|xi|=i⋅|x|

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

11

Concepto de Lenguaje Formal


Operaciones con palabras: 

Definición (Palabra inversa):





Sea x=A1A2...An con Ai∈Σ una palabra sobre el alfabeto Σ. Se llama palabra refleja o inversa de x, y se representa por x-1, a la palabra AnAn-1...A1. Si x=λ entonces x-1=λ. Ejemplos: x =abc ⇒ x-1=cba



Propiedades de la palabra inversa:


|x-1|=|x|

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

12

6

Concepto de Lenguaje Formal


Lenguajes Formales: 

Definición (Lenguaje universal):





Sea Σ un alfabeto. El lenguaje universal de Σ es el conjunto formado por todas las palabras que se pueden formar con las letras de Σ. Representamos dicho lenguaje con W(Σ). Ejemplos: 



Σ1 ={a}

⇒ W(Σ1)={λ, a, aa, aaa, ...}

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

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

13

Concepto de Lenguaje Formal


Lenguajes Formales: 

Definición (Lenguaje):


Sea un alfabeto Σ. Un lenguaje L sobre Σ es cualquier subconjunto del lenguaje universal W(Σ).




Ejemplos: Σ1 ={a} ⇒ W(Σ1)={λ, a, aa, aaa, ...} L1 ={a} ⊆ W(Σ1) L2 ={} ⊆ W(Σ1) (L2 = ∅) L3 =Σ1 ⊆ W(Σ1) L4 =W(Σ1) ⊆ W(Σ1) L5 ={λ} ⊆ W(Σ1) (Nota: L5≠L2) L6 ={λ, a, aaa, aaaaa} ⊆ W(Σ1) L7 ={λ, a, aaa, aaaaa, ...} ⊆ W(Σ1)



Hay lenguajes finitos, infinitos y vacíos.

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

14

7

Sumario: Capítulo 2: “Lenguajes Formales”




1. 2.

Concepto de Lenguaje Formal Operaciones sobre Lenguajes Formales (u otros conjuntos)

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

15

Operaciones con lenguajes (u otros conjuntos)


Unión: 

Definición (Unión de lenguajes):




Sea el alfabeto Σ y dos lenguajes L1⊆W(Σ) y L2⊆W(Σ). La unión de L1 y L2, L1∪ L2, es un lenguaje que se define de la siguiente forma: L1∪ L2={x|x∈ L1 o x∈ L2}.

Propiedades de la unión:


Operación cerrada: L1⊆W(Σ), L2⊆W(Σ) ⇒ L1∪L2⊆W(Σ) (la unión de dos lenguajes sobre el mismo alfabeto es también un lenguaje sobre este alfabeto)







Asociativa: (L1∪ L2) ∪ L3=L1∪(L2 ∪ L3) Elemento neutro: ∀L1, N ∪ L1 = L1 Conmutativa: L1∪ L2 = L2 ∪ L1 Idempotencia: L ∪ L = L

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

¿Que es N?

16

8

Operaciones con lenguajes (u otros conjuntos) Concatenación:




Definición (Concatenación de lenguajes):




Sean dos lenguajes L1, L2. La concatenación de L1 y L2, representado por L1L2 (a veces por L1.L2), es un lenguaje que se define de la siguiente forma: L1L2={xy | x∈ L1 , y∈ L2}.

Ejemplos: Σ ={a,b,c}



L1 ={ab, ac, cb}; L2={b, bba} ⇒ L1L2={abb,abbba,acb,acbba,cbb,cbbba} L1 ={a, aa, aaa, ...}; L2={λ, b, bb, bbb, ...} ⇒ L1L2=¿? ¿Qué pasa si L1 o L2 es ∅?

Propiedades de la concatenación








Cerrada: Asociativa: No es conmutativa: Elemento neutro({λ}): No es idempotente:

Universidad Rey Juan Carlos

L1⊆W(Σ), L2⊆W(Σ) ⇒ L1L2⊆W(Σ) (L1L2)L3 = L1(L2L3) ¬(∀L1, L2: L1L2=L2L1) ∀L1: L1{λ}={λ}L1=L1 ¬(∀L: LL=L)

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

17

Operaciones con lenguajes (u otros conjuntos) Potencia de un lenguaje:




Definición (Potencia de un lenguaje):




La potencia i-ésima de un lenguaje L consiste en el lenguaje resultante de concatenar el lenguaje consigo mismo i veces. Li = LLL...L (i veces)

Propiedades de la potencia






Cerrada: L ⊆ W(Σ) ⇒ Li ⊆ W(Σ) Li+1 = LiL = LLi (i>0) LiLj = Li+j (i,j>0)

¿Que pasa si i, j = 0?
Se define L0 = {λ} L0+1 = L1 = L = {λ}L=L0L L0L0= {λ}{λ} ={λ}=L0 = L0+0 Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

18

9

Operaciones con lenguajes (u otros conjuntos)


Potencia de un lenguaje: 

Ejemplos: L1 = {λ,ab, ac} ⇒ L12={λ,ab,ac,abab,abac,acab,acac} ⇒ L13={λ,ab,ac,abab,abac,acab,acac,ababab,ababac, abacab,abacac,acabab,acabac,acacab,acacac} L2 = {a, aa, aaa, ...} ⇒ L22=¿? ⇒ L23=¿?

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

Universidad Rey Juan Carlos

19

Operaciones con lenguajes (u otros conjuntos) Clausura de un lenguaje




Definición (Clausura positiva):




La clausura positiva de un lenguaje L se define por: ∞ i L+= Ui =1 L

Ejemplos:


L ={a,aa,aaa,aaaa,...} = {an | n≥1} ⇒ L2={ aa,aaa,aaaa,...} = {anam | n,m≥1} = {an | n≥2} ⇒ L3={ aaa,aaaa,...} = {anam | n≥1, m≥2} = {an | n≥3} ∞ i ⇒ L+= Ui =1 L ={a,aa,aaa,aaaa,...} = L




Σ={a,b}, Σ es un lenguaje sobre Σ, ya que Σ⊆W(Σ) ∞

Σ+= Ui =1 Σ ={a,b,aa,ab,ba,bb,aaa,...} = W(Σ) - {λ}



i

Nota: Si λ∉L, entonces λ∉L+.

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

20

10

Operaciones con lenguajes (u otros conjuntos) 

Definición (Clausura, Iteración o cierre):


La clausura de un lenguaje L se define por: ∞ L*= Ui =0 Li



Nota: ∀ L: λ∈L*, ya que {λ}=L0.



Propiedades de la clausura:




Cerrada: L⊆W(Σ)⇒ L+⊆W(Σ) , L*⊆W(Σ) ∞ i L*=L0∪(Ui =1 L )= L0∪L+={λ}∪L+ L+=LL*= L*L 

Demostración¿?

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

21

Operaciones con lenguajes (u otros conjuntos) Reflexión de un lenguaje






Definición (Reflexión):




Ejemplos:





Sea L un lenguaje. Se llama lenguaje inverso (lenguaje reflejo) de L, y se representa por L-1 al lenguaje: L-1={x-1|x∈L}.

L ={ana,julio,jesus,norma} ⇒ L-1={ana, oiluj,susej,amron} L ={a,aa,aaa,...} ⇒ ¿L-1?

Propiedades de la reflexión:


Cerrada: L⊆W(Σ) ⇒ L-1⊆W(Σ)

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

22

11

Operaciones con lenguajes (u otros conjuntos) Otras operaciones clásicas de conjuntos




Definición (Intersección):







Sean dos lenguajes L1 y L2. La intersección de L1 y L2, L1∩ L2, es el lenguaje que se define por: L1∩ L2={x|x∈ L1 y x∈ L2}.

Propiedades de la intersección






Cerrada: L1⊆W(Σ) , L2⊆W(Σ) ⇒ L1∩L2⊆W(Σ) Asociativa: (L1∩L2) ∩L3=L1∩ (L2∩L3) Conmutativa: L1∩L2= L2∩L1 Idempotencia: L∩L=L L∩∅=∅

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

23

Operaciones con lenguajes (u otros conjuntos) Otras operaciones clásicas de conjuntos




Definición (Complemento):




Sea L un lenguaje sobre el alfabeto Σ. El complemento de L, denotado con L (o con c(L)) es el siguiente lenguaje: L ={x|x∈W(Σ) y x∉L}

Propiedades del complemento




Cerrada: L⊆W(Σ) ⇒ W(Σ ) =∅ L =L

Universidad Rey Juan Carlos

L ⊆W(Σ)

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

24

12

Operaciones con lenguajes (u otros conjuntos) Otras operaciones clásicas de conjuntos




Definición (Diferencia):




Sean dos lenguajes L1 y L2. La diferencia de L1 y L2, L1- L2 (o L1\L2) es el lenguaje que se define por: L1- L2={x|x∈ L1 y x∉ L2}.

Propiedades de la diferencia






Cerrada: L1⊆W(Σ) , L2⊆W(Σ) ⇒ L1-L2⊆W(Σ) No es asociativa: ¬(∀ L1, L2: (L1-L2)-L3=L1-(L2-L3)) No es conmutativa: ¬(∀ L1, L2: L1-L2=L2-L1) No es idempotente: ∀ L: L-L=∅ A-∅=A

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

25

Operaciones con lenguajes (u otros conjuntos) Otras leyes de las operaciones sobre conjuntos




Leyes de De Morgan:





Leyes de complemento:










L∩ L =∅ L∪ L =W(Σ)

Distributividad:




L1∩ L2= L1 ∪ L 2 L1∪ L2= L1 ∩ L 2

L1∪(L2 ∩L3)= (L1∪L2)∩( L1∪L3) L1∩ (L2 ∪L3)= (L1∩L2) ∪ ( L1∩L3)

L1 -L2=L1∩ L 2 = L1 ∪ L 2 L =W(Σ)-L

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

26

13