Page 37 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

37

corrientes, toda vez que una cadena puede contener cualquier símbolo, en
consecuencia puede ser un operador.

 Longitud: volviendo al concepto anteriormente expuesto de longitud |w|. Es
importante advertir que |w1| ● |w2| = |w1|+ |w2| y si |w1|=|w2|=0 → |w| = 0
siendo entonces |w|= | є |.

 Número de ocurrencias de un símbolo: el número de apariciones de un símbolo
en una cadena w se denota por: | | donde x es el simbolo que se desea verificar

ocurrencia. Asi las cosas: si |w|=villalaz →| | = 3.

 Inversión: la inversión de una cadena es colocar la palabra en forma inversa. Si w

es una palabra o cadena, entonces denota la inversa. Así: W=villa → entonces

= alliv. Otro ejemplo si {011101} → |011101| = 101110. Debe ser obvio

que la inversa de la cadena vacía es ella misma. |є| = є . Note que ( | 1|●| 2|)

= | 2| ● | 1|
Compruébelo, cómo sería si: w1 = {loco} y w2 ={yo} Sería W = yo loco
R

 Palíndromos: un palíndromo es una cadena que su inversa es igual a la cadena
original. Esto lo dieron conmigo en la clase de aplicada ii, si lo recuerdan. La
cadena vacía, y todas las que tienen un solo símbolo son palíndromos y lo serian
cadenas como: salas, aba, amor a roma, y otras.

Volviendo sobre la definición de cadena, tenemos que insistir en que, una cadena w es una
sucesión finita de símbolos, sobre un alfabeto a. Lo cual se corresponde, como ya hemos dicho
con un conjunto, así las cosas, las operaciones entre cadenas están fundamentadas en las
operaciones de conjuntos. Y es importante recordar el concepto de la clausura sobre el alfabeto
A* el conjunto de todas las posibles cadenas sobre un alfabeto A, se describe como A* también
llamado Clausura de Kleene.

Donde es el conjunto de todas las cadenas de longitud i sobre a.

Resumiendo las operaciones son las ya mencionadas: concatenación, reversa, igualdad de
cadenas, y longitud de las cadenas. En este respecto anotar que la concatenación de cadenas no
es conmutativa y que en función de la cerradura de Klein, se puede expresar una cadena en función
de su k-esima potencia.