Alfabeto

Un alfabeto o vocabulario es un conjunto finito, no-vacío de símbolos (objetos atómicos o indivisibles).

Los alfabetos se denotan con una letra griega, usualmente Σ (Sigma).

Ejemplos

Alfabeto de dígitos decimales: Σ = {0,1,2,3,4,5,6,7,8,9}
Alfabeto de dígitos binarios: Β = {0,1}
Alfabeto de los caracteres: Α = {a, b,...z, A,...Z, ?, !...,*,$}

Cadena

Una cadena ω (también palabra, frase o sentencia) es una sucesión finita de símbolos, sobre un alfabeto Σ.

Una cadena es

ω = s ₁ s ₂... s _n donde s ₁,s ₂,... s _n ∈ Σ
y el símbolo s _i 1 ≤ i ≤ n, ocurre en la posición i de la cadena.

Cadena Vacía

Por convención, ε denota la cadena vacía (la cadena que no tiene símbolos).

Ejemplos

Si Β = {0,1}, son cadenas sobre Β:

α₁ = 0101
α₂ = 1111
α₃ = 0111000
α₄ = ε

Operaciones sobre Cadenas

Sean dos cadenas sobre el alfabeto Α

ω=a ₁,a ₂,... a _n y η=b ₁,b ₂,... b _m a _i,b _j ∈ Α

Longitud de una cadena:

|ω| denota la longitud de la cadena ω

Igualdad

ω=η si |ω|=|η| y (∀i: i 1 ≤ i ≤ |ω|: a _i=b _i)

Reversa

ω^R denota la reversa de la cadena ω
ω^R = a _n, a _n-1,... a ₂, a ₁

Concatenación

ω⋅η denota la concatenación, la cual consiste en la en la secuencia de símbolos de ω seguidos de los de η
ω⋅η = a ₁,a ₂,... a _n, b ₁,b ₂,... b _m

Exponenciacion

ω^k denota la concatenación de ω con si misma k-1 veces
ω⁰ = ε, la Cadena vacía
ω^k=ω^k-1⋅ω

Ejemplos

A continuación se calculan algunas operaciones para las cadenas α₁, α₂, α₃, y α₄ del ejemplo dado en la definición de cadenas:

Longitud

• |α₁| = |0101| = 4
• |α₄| = |ε| = 0

Reversa:

• α₁^R = 1010

Concatenación

• α₁⋅α₂ = 01011111
• α₂⋅α₄ = 1111
• α₂⋅α₂ = 11111111

Potencia

• α₂³ = α₂⋅α₂⋅α₂ = 111111111111
• α₁⁴ = 0101010101010101

Clausura

Definimos Σ^*, la Clausura sobe Σ, como el conjunto de todas las posibles cadenas finitas sobre un Alfabeto Σ. Se conoce también como Clausura de Kleene, se denota como Σ^*, y se define así:

ε ∈ Σ^* ; la cadena vacía pertenece a la clausura
a ∈ Σ ⇒ a ∈ Σ^* _; todo elemento en Σ pertenece a la clausura
ω, η ∈ Σ ⇒ ω⋅η ∈ Σ^* ; la concatenación de cualquier par de elementos en la clausura también pertenece a la clausura

Formalmente, la clausura constituye un monoide sobre el conjunto Σ y la operación de concatenación.

Otras definiciones útiles

Definimos:

• Σ^k como todas las cadenas sobre Σ de longitud k:
  Σ^k = ω ∈ Σ^*, |ω| = k
• Σ⁺ como todas las cadenas sobre Σ de longitud mayor o igual a uno:
  Σ⁺ = Σ^* - {ε}

Lenguaje

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