Hsilva

DEFINICIONES PREVIAS

En este capítulo se introducen un conjunto de definiciones elementales necesarias para los desarrollos teóricos posteriores. Se definen de forma intuitiva, especificándose algunas de ellas de manera formal en capítulos posteriores.

Símbolo

Es una entidad abstracta, que no se va a definir, pues se dejará como axioma. Al igual que no se define punto en Geometría.Normalmente los símbolos son letras (a, b, c, . . . ,z), dígitos (0, 1, . . ., 9), y otros caracteres (+, -, *, /, ?, . . .). Los símbolos también pueden estar formados por varias letras o caracteres, así por ejemplo las palabras reservadas de un lenguaje de programación son símbolos de dicho lenguaje.

Ejemplos

a , b , c , # , 0 , 1 , + , * ,then, begin, end, else

Vocabulario o alfabetoEs un conjunto finito de símbolos, no vacío. Para definir que un símbolo a pertenece a un alfabeto V se utiliza la notación a V. Los alfabetos se definen por enumeración de los símbolos que contienen, así por ejemplo se presentan a continuación varios alfabetos.

Ejemplos
V1 = { A , B , C , D , E , F , G , H, . . . , X , Y , Z }
V2 = { a , b , c , d , 0 , 1 , 2 , 3 , 4 , * , # , + }
V3 = {0 , 1 }
V4 = {if, then, begin, end, else, a, b, ; , =, > }

También se puede definir las tablas ASCII y EBCDIC como los alfabetos de distintos ordenadores.

Cadena
Una cadena es una secuencia finita de símbolos de un determinado alfabeto.
Ejemplos

Se utilizan los vocabularios de los ejemplos del epígrafe 2.2.1.
abcb es una cadena del alfabeto V2
a+2*b es una cadena del alfabeto V2000111 es una cadena del alfabeto V3
if a>b then b=a; es una cadena del alfabeto V4




Longitud de cadena

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

Ejemplos

Se utilizan las cadenas de los ejemplos del epígrafe 2.3.1.
abcb 4
a 2*b 5
000111 6
if a b then a b ;9


Cadena vacía

Existe una cadena denominada cadena vacía, que no tiene símbolos y se denota con, entonces su longitud es:



Concatenación de cadenas

Sean α y β dos cadenas cualesquiera, se denomina concatenación de α y β a una nueva cadena constituida αβ por los símbolos de la cadena seguidos α por los de la cadena β.
El elemento neutro de la concatenación es λ:



Universo deldiscurso

El conjunto de todas las cadenas que se pueden formar con los símbolos de un alfabeto V se denomina universo del discurso de V y se representa por W(V). Evidentemente W(V) es un conjunto infinito. La cadena vacía pertenece a W(V).

Ejemplo

Sea un alfabeto con una sola letra V = { a }, entonces el universo del discurso es :

W(V) = { , a, aa, aaa, aaaa, . . . }

Que contieneinfinitas cadenas.

Lenguaje

Se denomina lenguaje sobre un alfabetoVa un subconjunto del universo del discurso. También se puede definir como un conjunto de palabras de un determinado alfabeto.

Alguien puede pensar que los lenguajes se pueden definir porenumeración de las
Cadenas que pertenecen a dicho lenguaje, pero este método además de ineficiente, es en
Muchos casos imposibles(habitualmente un lenguaje tiene infinitas cadenas). Así los
lenguajes se definen por las propiedades que cumplen las cadenas del lenguaje.


Ejemplo 2.8.1
El conjunto de palíndromos (cadenas que se leen igual hacia adelante, que hacia
atrás) sobre el alfabeto {0,1}. Evidentemente este lenguaje tiene infinitas cadenas.
Algunas cadenas de este lenguaje son:
0
1
00
11
010
0110
000000101101
111111


Lenguaje vacío

Existe un lenguaje denominado el lenguaje vacío, que es un conjunto vacío y que se denota por {Ø }. El lenguaje vacío no debe confundirse con un lenguaje que contenga una sola cadena, y que ésta sea la cadena vacía, es decir {λ }, ya que el número de elementos (cardinalidad) de estos dos conjuntos es diferente.
Cardinal ({Ø }) = 0
Cardinal ({λ }) = 1...