Operadores compiladores

Tema 1: Lenguajes. Gramáticas
´ ´ Departamento de Sistemas Informaticos y Computacion

DSIC - UPV

http://www.dsic.upv.es – p.1/12

Tema 1: Generalidades sobre lenguajes formales
•Definiciones. Alfabeto, palabra, lenguaje. • Operaciones con lenguajes: ◦ Booleanas. ◦ Concatenación. Potencia. Cierre estrella. ◦ Cocientes. ◦ Reverso. ◦ Sustitución. Homomorfismo. Homomorfismo inverso.

DSIC -UPV

http://www.dsic.upv.es – p.2/12

Definiciones
• Alfabeto • Palabra, cadena o frase • Palabra vacía • Longitud de una palabra: |x| = 0 si x = λ |y|+1 si x = ya; a ∈ Σ, y palabra sobre Σ ej. Σ= {a, b, c} ej. x = abbabba λ

• Concatenación: siendo x = a1 , a2 , . . . , am , y = b1 , b2 , . . . , bn , se define xy = a1 , a2 , . . . , am , b1 , b2 , . . . , bn Propiedades ◦ Asociativa ◦Elemento neutro (λ)

DSIC - UPV

http://www.dsic.upv.es – p.3/12

Definiciones
• Σn : Conjunto de todas las palabras de longitud n sobre Σ • Monoide libre asociado a Σ: Σ∗ = Σi
i≤0

• Lenguaje:cualquier subconjunto de Σ∗ ◦ ejs. ... • Reverso de una palabra: x = Propiedades: ◦ (xy)r = y r xr ◦ (xr )r = x
r

x ay r

si x = λ si x = ya, a ∈ Σ, y ∈ Σ∗

DSIC - UPVhttp://www.dsic.upv.es – p.4/12

Operaciones con lenguajes
• Booleanas ◦ Union: ◦ Intersección: ◦ Complementación: • Diferencia • Diferencia simétrica L1 ∪ L2 = {x ∈ Σ∗ | x ∈ L1 ∨ x ∈ L2 } L1 ∩ L2 = {x ∈ Σ∗ | x ∈ L1∧ x ∈ L2 } L = {x ∈ Σ∗ | x ∈ L} L 1 − L2 = L1 ∩ L 2 L1 L2 = (L1 − L2 ) ∪ (L2 − L1 )

DSIC - UPV

http://www.dsic.upv.es – p.5/12

Operaciones con lenguajes
• Concatenación de lenguajes: L1 · L2= {xy ∈ Σ∗ | x ∈ L1 ∧ y ∈ L2 } Propiedades: ◦ No conmutativa: L 1 · L 2 = L2 · L 1 ◦ Asociativa: L1 · (L2 · L3 ) = (L1 · L2 ) · L3 ◦ Anulador: L·∅=∅ ◦ Distributiva respecto de la unión: L1 · (L2 ∪ L3) = (L1 · L2 ) ∪ (L1 · L3 ) ◦ No distributiva respecto la intersección: L1 · (L2 ∩ L3 ) ⊆ (L1 · L2 ) ∩ (L1 · L3 )

DSIC - UPV

http://www.dsic.upv.es – p.6/12

Operaciones con lenguajes...