Alfabetos

Σ : alfabeto, Conjunto finito, no vacio de símbolos.

Cadena: sucesión de símbolos concatenados.

Σ¹ = Σ

Σⁿ⁺¹ = { xy / x ∈ Σ, y ∈ Σⁿ } ; donde x, y son cadenas formadas por símbolos de Σ.
Aclaración: en este caso x representa una cadena formada por un solo símbolo de Σ.

Ejs:
Σ = {a,b,c} => Σ² = {aa, ab, ac, ba, bb, bc, ca, cb, cc }
aab ∈ Σ³

Cardinalidad de un Alfabeto

| Σ | = 3  => | Σ²| = 3²

Generalizando:

| Σ | = t  => | Σⁿ| = tⁿ

Cadena Vacia

λ: Cadena o palabra vacia. Elemento neutro para la concatenación de cadenas.

Importante: ∀Σ:  Σ⁰= { λ }

Conjunto infinito de todas las cadenas que pueden formarse con un alfabeto

Σ^* = $\underset{n=0}{\bigcup ^{\infty }}\Sigma { }^n$  
| Σ | = ∞

Cadenas y Concatenación

Se puede definir una cadena W sobre el alfabeto Σ como: W = x₁x₂…..x_n ; x_i ∈ Σ

Longitud de una cadena

|| w || = n

Concatenación

Sean:
X = x₁x₂…..x_n ; x_i ∈ Σ
Y = y₁y₂…..y_m ; y_i ∈ Σ
=>
XY = x₁x₂…..x_ny₁y₂…..y_m; ∧ XY ∈ Σ^{n + m}

Propiedades de la Concatenación

1. Cerrada sobre si misma (Ley de Composición Interna)
Σ^* -> Σ^* : Σ^*

2. Asociativa
X(YZ) = (XY)Z

3. No Conmutativa
XY ≠ YX

Longitud de una Concatenación

|| XY || = || X || + || Y ||; ∀ X, Y ∈ Σ^*

Potencias de una cadena

∀ X ∈ Σ^*:
X⁰ = λ
X¹ = X
X² = XX
Xⁿ = XX^{n - 1}
|| Xⁿ|| = n . || X ||

Prefijos, Sufijos

sea W ∈ Σ^* ∧ W = XY entonces X es prefijo de W, Y es sufijo de W.
Si adémas:
Y ≠ λ => X es prefijo propio de W
X ≠ λ => Y es prefijo propio de W  

Subcadenas

sea W ∈ Σ^* ∧ W = XZY entonces Z es subcadena de W.

Lenguajes

Sea Σ ≠ φ, L ⊆ Σ^* es un lenguaje sobre Σ

Importante: φ ⊂ Σ . φ es un lenguaje, llamado lenguaje Vacio.

Gramática

G = (V, T, S, P) es una gramática donde:
V  es un Alfabeto
T ⊂ V, son los elementos terminales
S ⊂ V, es el Start Symbol. O Simbolo de Comienzo.
P, son las reglas de Producción.

Lenguaje generado por una gramática

Todas las cadenas de elementos pertenecientes a T, que pueden formarse a partir de las reglas de Producción P. Se lo suele representar com L_{( G )} .

Ejemplos

1) L = { 1111ⁿ0ⁿ / n ∈ N}. Lenguaje formado por todas las cadenas con prefijo 111 y luego una suseción de 10.

G = ( V,T,S₀,P )
V = {1,0,S}
T = {1,0}
S₀ = S
P:
S -> S10
S -> 111S

2) L = Lenguaje formado por todas las cadenas con prefijo 111 y luego  al menos un 1 o un 0 y luego una sucesión de 1s y 0s en cualquier orden. = {1110, 1111, 11101, 11100, 11110, 11111, …. }

G = ( V,T,S₀,P )
V = {1,0,S,A,B}
T = {1,0}
S₀ = S
P:
AB -> BA
BA -> AB
A -> 0
B -> 1
S -> SA
S -> SB
S -> 111S

3) L = Lenguaje que tiene la misma cantidad de 0s y 1s. = { λ, 01, 10, 0011, 0110, 1100, 0101, 1010, …. }

G = ( V,T,S₀,P )
V = {1,0,S, A, B}
T = {1,0}
S₀ = S
P:
AB -> BA
BA -> AB
A -> 0
B -> 1
S -> SAB
S -> λ

Referencias

Apuntes de Clase de Algebra y Matemática Discreta cursada en el segundo cuatrimestre de 2007 en la Universidad de Palermo dictada por Marcela Wilder.
Algebra Y Matenática Discreta, Gabriela Esperón, Marcela Wilder, UP, 2007.