Lenguajes y operaciones con lenguajes

1. Lenguajes y operaciones con lenguajes

A continuación, se presentan diferentes operaciones que se pueden definir sobre los lenguajes.

1. Unión de lenguajes La unión de dos lenguajes L1 y L2 definidos sobre el mismo alfabeto Σ es otro lenguaje, también definido sobre ese alfabeto, que contiene todas las palabras de L1 y todas las deL2.

L = L1 ∪ L2  = { x/x ∈ L1 ∨ x ∈ L2}

Propiedades:

• Operación cerrada. El lenguaje resultante está definido sobre el mismo alfabeto que L1 y L2.
• Asociativa. (L1 ∪ L2 ) ∪ L3 = L1 ∪ ( L2 ∪ L3 ).
• Conmutativa. L1 ∪ L2 = L2 ∪ L1
• Elemento Neutro (Ø).    L ∪ Ø = Ø ∪ L = L
• Idempotencia. L ∪ L = L.

1. Concatenación Sean dos lenguajes L1 y L2 definidos sobre el mismo alfabeto Σ, la concatenación de ambos lenguajes estará formada por todas las palabras obtenidas al concatenar una palabra cualquiera de L1 con otra de L2.

L = L1 L2 = { xy / x ∈ L1 ∧ y ∈ L2}

Propiedades:

• Operación cerrada. El lenguaje resultante está definido sobre el mismo alfabeto que L1 y L2.
• Asociativa. ( L1 L2 ) L3 = L1 ( L2 L3).
• Elemento Neutro ( Lλ = {λ} ).     L λ L = L L λ= L
• No es conmutativa.

1. Potencia i–esima Es el resultado de concatenar un lenguaje consigo mismo un número i de veces. Li = L...iL

Propiedades:

• Li + j = Li Lj
• L0 = Lλ = {λ}

1. Clausura (o cierre de Kleene) La clausura de un lenguaje (L∗) es el resultado de unir todas las potencias de dicho lenguaje, es decir, [pic 1]

1. Clausura positiva La clausura positiva de un lenguaje (L+) es la unión de todas las potencias de ese lenguaje, exceptuando la potencia cero.

[pic 2]

Propiedades:

• L ∗ = L + ∪ {λ}
• L + = L ∗ L = LL∗
• ω (Σ) = Σ ∗

En este caso el alfabeto es considerado como un lenguaje, concretamente el formado por todas las cadenas de longitud 1.

• Σ + = Σ ∗ \ {λ}

1. Reflexiòn La reflexión de un lenguaje (         )  está formada por las inversas de todas las palabras de ese lenguaje. [pic 3][pic 4]

1. Concepto de gramática formal

Los primeros trabajos de gramática aparecen en la India, alcanzándose el máximo grado de perfección con Panini (siglos VII y VI a. C.). Al mismo tiempo en Grecia se desarrollaba investigación gramatical, representante Pitágoras. Sin embargo, el concepto de gramática tiene su origen en los trabajos de Noam Chomsky lingüista, filósofo y activista quien propuso la gramática generativa a mediados del siglo XX.

...