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 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 2.4.1

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

2.5 Cadena vacía

Existe una cadena denominada cadena vacía, que no tiene símbolos y se denota con

λ , entonces su longitud es :

| λ |→ 0

2.6 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 λ :

αλ = λα = α

...