Automatas

INGENIERÍA TÉCNICA en INFORMÁTICA de SISTEMAS y de GESTIÓN de la UNED
ASIGNATURA: TEORÍA DE AUTÓMATAS I
Tutoría del Centro Asociado de Plasencia

EJERCICIOS DE LA SECCIÓN 1.1
1.- Diseñe un diagrama de transiciones para reconocer expresiones aritméticas de longitud arbitraria que comprenden enteros
positivos separados por signos de suma, resta, multiplicación o división.
Solución:
dígito1
operador

dígito
operador
2

dígito
3

letra

dígito
4

operador

letra

letra

letra
operador

error
operador = ‘+’, ‘-‘, ‘*’, ó ‘/’

Comentarios:
1º No puede comenzar recibiendo un operador, por dos razones:
1ª Está especificado que los números son positivos.
2ª Si se empieza admitiendo un operador, es estaría admitiendo que la cadena empezara con * ó /.
2º En eldiagrama dado se llega al estado de aceptación tras leer dos y sólo dos números enteros de longitud arbitraria.
Si el número de operaciones pudiera ser mayor que una, tendríamos un arco del estado 4 al 3 con etiqueta operador:
dígito
1
operador

dígito
operador
2

letra

dígito
3

letra

letra
error

operador

dígito
4

operador
letra

operador

operador = ‘+’, ‘-‘,‘*’, ó ‘/’

Ejercicios de Teoría de Autómatas I

1

José Garzía

2.- Escriba un analizador léxico directamente a partir del siguiente diagrama de transiciones:
dígito

letra
2

letra


1

=

3

4

dígito
dígito

5

Solución:
Estado := 1;
Leer el siguiente símbolo de entrada
WHILE El último símbolo leído no sea el de Fin de Cadena DO
CASE Estado OF
1: CASE Símboloactual OF
Letra : Estado := 2 ;
‘:’
: Estado := 3 ;
Dígito : Estado := 5 ;
ELSE
Salir a rutina de error ;
END (* del CASE interno *)
2: CASE Símbolo actual OF
Letra : Estado := 2 ;
Dígito : Estado := 2;
ELSE
Salir a rutina de error ;
END (* del CASE interno *)
3: IF Símbolo actual ‘=‘

THEN

Salir a rutina de error

END ;

4: IF Símbolo actual NIL

THEN

Salir a rutinade error

END ;

5: IF Símbolo actual dígito

THEN

Salir a rutina de error

END ;

ELSE Salir a rutina de error ;
END (* del CASE externo *)
END (* del WHILE *)
IF ( Estado=1 OR Estado=3 ) THEN Salir a rutina de error END ;

3.- Construya una tabla de transiciones a partir del diagrama del ejercicio anterior y escriba un analizador léxico basado en la tabla.
Solución:
TABLADE TRANSICIONES
Símbolo
letra
Estado
1
2
3
4
5

2
2
Error
Error
Error

dígito
5
2
Error
Error
5

‘:’

‘=‘

3
Error
Error
Error
Error

Error
Error
4
Error
Error

ANALIZADOR LÉXICO
Estado := 1 ;
REPEAT
Leer el siguiente símbolo de entrada ;
CASE Símbolo OF
0..9
: Entrada := dígito ;
a..z, A..Z
: Entrada := letra ;
‘:’
: Entrada := ‘:’ ;
‘=’
: Entrada:= ‘=’ ;
Marca de fin de cadena : Entrada := FDC ;
ELSE
Salir a rutina de error ;
END (* del CASE *)
Estado := Tabla( Estado, Entrada ) ;
IF Estado=error THEN Salir a rutina de error END ;
UNTIL Estado=aceptar ;
Ejercicios de Teoría de Autómatas I

2

FDC
Error
Aceptar
Error
Aceptar
Aceptar

INGENIERÍA TÉCNICA en INFORMÁTICA de SISTEMAS y de GESTIÓN de la UNED
ASIGNATURA:TEORÍA DE AUTÓMATAS I
Tutoría del Centro Asociado de Plasencia

4.- Muestre que se puede modificar un diagrama de transiciones que contiene un arco rotulado por una cadena de símbolos de
longitud dos o más (lo cual significa que para recorrer el arco se requiere la cadena completa y no un sólo símbolo) para que
contenga sólo arcos rotulados con símbolos simples, pero de manera que siga aceptandolas mismas cadenas que antes.
Solución:
Inicialmente:
x1 x2 ... xn-1 xn
I

F

Pero si añadimos nuevos estados intermedios de la forma:
x1
I

x2
S2

xn-1
S3

...

xn
Sn

F

Es decir, de forma que:
Si estando en el estado I recibe la entrada x1, cambia al estado S2.
Si estando en el estado Si recibe la entrada xi, cambia al estado Si+1 (I=2,3, ..., n-1).
Si estando...