This page last changed on Oct 08, 2006 by juanca.

Un lenguaje formal L sobre un Alfabeto Σ es un subconjunto de Σ* (la Clausura sobre Σ). Es decir, un lenguaje L es cualquier conjunto de cadenas finitas sobre el Alfabeto Σ:

LΣ*

Ejemplos

Los siguientes son Lenguajes sobre Σ = {0,1}

La = ∅, lenguaje finito vacío.
Lb = {ε}, lenguaje finito que contiene sólo la cadena vacía.
Lc = {0,1}, lenguaje finito que contiene sólo las cadenas de longitud 1.
Ld = {0,00,000,0000,...}, lenguaje infinito que consiste de cadenas con cualquier cantidad de símbolos 0.
Le = {0 n 1 n / n ≥ 1} = {01,0011,000111,00001111,...}, lenguaje infinito que consiste de cadenas que comienzan con una cantidad de símbolos 0, seguidos por la misma cantidad de símbolos 1

Operaciones sobre Lenguajes

Dados dos lenguajes La y Lb sobre el alfabeto Σ, se definen las siguientes operaciones cada una de las cuales produce un nuevo lenguaje sobre Σ:

Unión

La ∪ Lb = {ω ∈ Σ* / ω ∈ La ∨ ω ∈ Lb }

Intersección

La ∩ Lb = {ω ∈ Σ* / ω ∈ La ∧ ω ∈ Lb }

Diferencia

La - Lb = {ω ∈ Σ* / ω ∈ La ∧ ω ∉ Lb }

Complemento

-L = {ω ∈ Σ* / ω ∉ L }

Reverso

L R = {ωR / ω ∈ L }

Concatenación

La⋅Lb = { ω⋅η / ω, η ∈ Σ*, ω ∈ La ∧ η ∈ Lb }

Potenciación

L 0 = {ε}
L 1 = L
L k = L k-1⋅L

Clausura

L 0 ⊆ L *
L ⊆ L *
La,Lb ∈ L * ⇒ La⋅Lb ∈ L *

Propiedades

Si L, La, Lb, y Lc son lenguajes sobre Σ, entonces se cumple que:

  1. Elemento Neutro
    L⋅∅ = ∅ = ∅⋅L
  2. Asociativa de la Concatenación
    (La⋅Lb)⋅Lc = La⋅(Lb⋅Lc)
  3. Distributiva de la Concatenación respecto a la Unión
    La⋅(Lb∪Lc) = La⋅Lb ∪ La⋅Lc
Document generated by Confluence on Oct 04, 2010 11:25