1.2 Cadenas

Una cadena o palabra sobre un alfabeto Σ. admitimos la existencia de una única cadena que no tiene símbolos, la cual se denomina cadena vacía y se denota con λ. la cadena vacía desempeña, en la teoría de lenguajes formales, un papel similar al que desempeña el conjunto vacío Ø en la teoría de conjuntos.

Longitud de cadena.

La longitud de cadena es el número de símbolos que contiene. La notación empleada es la que es la que se indica en el ejemplo.

Utilizamos las cadenas de los ejemplos:

I abcb I = 4,

I a + 2*b I = 5

I 000111 I = 6

I if a > b then a = b; I = 9

Cadena Vacía

Una cadena vacía es la única cadena de caracteres de tamaño cero. Y la podemos denotar usualmente con letras λ o Є (Griegas).

Concatenación de cadenas.

La concatenación de dos cadenas u y v, escrita uv, es "pegar" las dos cadenas para formar una nueva.

Ejemplo:

Sea u = ab

v = ca

w = bb. Entonces

uv = abca

uw = cabb

(uv) w = abcabb

u(vw) = abcabb

El resultado de la concatenación de u, v y w es independiente del orden en que las operaciones son ejecutadas. Matemáticamente esta propiedad es conocida como asociatividad.

Universo del discurso

Es un conjunto de todas las cadenas donde podemos formar con símbolos del alfabeto V le denominamos universo del discurso de V y la representamos de la siguiente manera W (V). Es evidente que W(V) es un conjunto infinito y que la cadena vacía pertenece a W(V).

Ejemplo:

Un alfabeto con una sola letra V = { a }, podemos decir que el universo del discurso es: W(V) = { λ, a, aa, aaa, aaaa,....} y así contiene una cadenas infinitas.

¿Qué es un lenguaje?

Informalmente: un lenguaje es un conjunto de palabras o sentencias formadas sobre un alfabeto.

1.1 Alfabeto:

Definición (Alfabeto):

Conjunto finito, no vacío, de elementos.

Generalmente usaremos Σ para especificar alfabetos y los elementos los denominaremos “letras” o “símbolos”.

Ejemplos: Los alfabetos español, inglés, o alemán

Σ1={0,...,9}, 0 ∈Σ 1

Σ2={x | x es un símbolo del código ASCII}

Σ3={(, )}

Σ4={1, A, 2, B}

Σ5={a, b, c, d}

Σ6={}

Σ7=ℵ

Concepto de Lenguaje Formal

Definición (Palabra):

Sea un alfabeto Σ. Una palabra sobre Σ es una secuencia finita de las letras de ese alfabeto.

La secuencia vacía representa la palabra vacía y la anotamos con λ.

Ejemplos: sobre Σ5 ={a,b,c,d}: λ, a, b, c, d, abc, aab, dcba, ... sobre Σ1 ={0,...,9}: λ, 0, 0000, 010, 9980, ... sobre Σ3 ={(,)} λ, (, ), (), (()()), )())), ...