Bloque de Colores

Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Icono de Post March 3 2012 :: Combinatoria, Lenguajes Formales, Lógica ::

Lo que estamos buscando es, dado A un alfabeto de tamaño k, la cantidad de cadenas de tamaño n que contienen exactamente m símbolos de A.

Para resolver este problema primero vamos a resolver lo siguiente:

Cuantas cadenas de tamaño n pueden ser creadas con todos los símbolos de un alfabeto de k símbolos?

Se propone la siguiente relación de recurrencia de 2 variables, donde:

n: representa el tamaño de la cadena

k: representa la cantidad de símbolos en el alfabeto

f(0, k) = 0

Para todo k, ya que la cantidad de cadenas de tamaño 0 que pueden formarse con todos los símbolos de A es 0.

f(1, 1) = 1

Ya que existe solo una cadena de tamaño 1 con 1 símbolo.

f(n, k) = k( f(n-1,k) + f(n-1, k-1) )

Demostración

Llamemos An,k al conjunto de todas las cadenas de tamaño n que contienen a todos los símbolos de A e intentemos construir todas las cadenas que pertenecen a este conjunto.

Para cada símbolo a de An,k vamos a realizar el siguiente procedimiento:

1. Llamemos An-1,k al conjunto de todas las cadenas de tamaño (n-1) con exactamente k símbolos de A (o sea con todos los símbolos de A).

Para cada cadena α de An-1,k construimos una nueva cadena concatenandole a, nos queda así una nueva cadena: . Como α tiene tamaño (n-1), la nueva cadena tiene tamaño n.

Ademas por definición de An-1,k, α contiene a todos los símbolos de A, y en particular contiene a a. Entonces de esta manera hemos formado todas las cadenas de An,k que comienzan por a y tienen al menos 2 ocurrencias de a.

Nos queda todavía construir todas las cadenas de An,k que comienzan por a pero tienen solo una ocurrencia de a.

2. Llamemos An-1,k-1 al conjunto de todas las cadenas de tamaño (n-1) que están formadas por todos los símbolos de A menos a.

Para cada cadena β de An-1,k-1 construimos una nueva cadena . Se cumple entonces que tiene tamaño n y ademas dado que β contiene a todos los símbolos de A menos a a y le hemos concatenado a, contiene los k símbolos de A.

A partir de estos dos pasos hemos construido todas las cadenas de An,k que comienzan con a. Como por definición de An,k, cualquier cadena de An,k necesariamente tiene que comenzar con un símbolo de A y a es un elemento arbitrario podemos aplicar el procedimiento para construir todas las cadenas del conjunto An,k.

Como por hipótesis, |An-1,k-1| = f(n-1,k-1), |An-1,k| = f(n-1,k) y como existen exactamente k símbolos de A se cumple que f(n, k) = k( f(n-1,k) + f(n-1, k-1) ).

Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Asumiendo que la función anterior es correcta, podemos proponer la siguiente función:


g

(
n
,
m
,
k
)

=

(

m
k

)

×
f

(
n
,
m
)


Llamemos Am al conjunto de todos los subconjuntos de A con exactamente m elementos. Es conocido que la cantidad de subconjuntos de tamaño m de un conjunto se puede calcular como:


|

A
m

|
=

(

m
k

)


(Ver Combination) . Sabemos ademas por el resultado anterior que la cantidad de cadenas de tamaño n que pueden hacerse de un conjunto de tamaño m es igual a f(n,m), a partir de lo cual derivamos la formula.

Autor: Emiliano Martínez Luque.

Comments Off on Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Alfabetos, Lenguajes y Gramáticas (Definiciones Básicas)

Icono de Post September 6 2008 :: Apuntes, Lenguajes Formales ::

Alfabetos

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

Cadena: sucesión de símbolos concatenados.

Σ1 = Σ

Σn+1 = { xy / x ∈ Σ, y ∈ Σn } ; 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} => Σ2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc }
aab ∈ Σ
3

Cardinalidad de un Alfabeto

| Σ | = 3  => | Σ2| = 32

Generalizando:

| Σ | = t  => | Σn| = tn

Cadena Vacia

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

Importante: ∀Σ:  Σ0= { λ }

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

Σ* = n = 0 Σ n   
| Σ | = ∞

Cadenas y Concatenación

Se puede definir una cadena W sobre el alfabeto Σ como: W = x1x2…..xn ; xi ∈ Σ

Longitud de una cadena

|| w || = n

Concatenación

Sean:
X = x1x2…..xn ; xi ∈ Σ
Y = y
1y2…..ym ; yi ∈ Σ
=>
XY = x
1x2…..xny1y2…..ym; ∧ 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
0 = λ
X
1 = X
X
2 = XX
X
n = XXn – 1
|| X
n|| = 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 = { 1111n0n / n ∈ N}. Lenguaje formado por todas las cadenas con prefijo 111 y luego una suseción de 10.


G = ( V,T,S0,P )
V = {1,0,S}
T = {1,0}
S
0 = 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,S0,P )
V = {1,0,S,A,B}
T = {1,0}
S
0 = 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,S0,P )
V = {1,0,S, A, B}
T = {1,0}
S
0 = 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.

Autor: Emiliano Martínez Luque.

Comments Off on Alfabetos, Lenguajes y Gramáticas (Definiciones Básicas)