Page 36 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

36

símbolos pertenecientes a ese alfabeto especificado. Será una cadena de ese alfabeto además,
incluye la cadena vacía.

En lenguajes formales una cadena suele describirse por la letra ω.
La cadena vacía:

La cadena vacía es aquella cadena que presenta cero apariciones de símbolos. Esta cadena,
obviamente, es una cadena que puede construirse en cualquier alfabeto. Generalmente se designa
como є o λ.
Longitud de una cadena:

Es útil clasificar las cadenas por su longitud, es decir, el número de posiciones ocupadas por
símbolos dentro de la cadena. Por ejemplo 01101 tiene una longitud de 5. Es habitual decir que
la longitud de una cadena es igual al “número de símbolos” que contiene, sin embargo, a pesar de
ser aceptada no es estrictamente correcta.
La notación estándar para indicar la longitud de una cadena w es |w|. Por ejemplo, |011| = 3

y | є | = 0. Esto lo deben recordar de matemáticas discreta, porque en resumen una cadena no es
más que un conjunto finito de caracteres que pertenecen a un alfabeto, que también es finito. Sin
embargo el número de cadenas posibles de ese conjunto alfabeto, es decir el conjunto potencia
deberá ser infinito, si consideramos lo anterior.

Subpalabras, prefijos y sufijos:

Las subsecuencias de una cadena o palabra son subpalabras o subcadenas de la cadena. Así, existe
el prefijo y el sufijo de la palabra o cadena. Se considera subpalabras impropias las palabras o
cadenas vacías y la entera; el resto se denominan o se consideran propias. Así las cosas los
prefijos y sufijos son subpalabras propias, con excepción de la cadena vacía y la entera.

Ejemplo: villa
El primer sufijo: є, v, vi, vil, villa

Operaciones y propiedades:

Existen algunas operaciones que se pueden realizar sobre los conjuntos, por tanto sobre los
alfabetos y sus cadenas o palabras. Estas son:

 Concatenación: como ya sabemos, realizar una concatenación de 2 palabras o
cadenas es construir una sola cadena añadiendo la cadena 2 a la cadena 1, justo
detrás de la cadena 1. Dicho de otra forma, añadir los símbolos de la segunda
cadena tras los símbolos de la primera. La concatenación suele expresarse por un
punto (● ) asi si concatenamos las cadenas {santa} y {ana}, seria: santa ● ana =
santaana si se solicitara la concatenación de la cadena santaana con la cadena vacía,
o sea santaana ● є = santaana. Válido anotar que la propiedad conmutativa, no es
válida en el tratamiento de cadenas toda vez que a ● b ≠ b ● a. Hay que anotar que
se aplica entre cadenas la propiedad asociativa y se considera la cadena vacía el
elemento neutro de la concatenación. La concatenación de una cadena consigo
2
misma se expresa por una exponenciación y se designa así: , siendo w la cadena
o palabra obviamente. Deberá entenderse que: = w●w. La concatenación de
2
una palabra y un símbolo, se denota igual que la concatenación de 2 cadenas