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 ⁿ 1 ⁿ / 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 ⁰ = {ε}
L ¹ = L
L ^k = L ^k-1⋅L

Clausura

L ⁰ ⊆ 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