Definiciones previas

CAPÍTULO 2: 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.

2.1 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.

2.1.1 Ejemplos

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

2.2 Vocabulario o alfabeto

Es un conjunto finito de símbolos, no vacio. 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 2.2.1

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.

2.3 Cadena

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

-3-

LENGUAJES, GRAMÁTICAS Y AUTOMATAS

Ejemplos 2.3.1

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 V2

000111 es una cadena del alfabeto V3

if a>b then b=a; es una cadena del alfabeto V4

2.4

...