Introducción:

	La práctica consiste en 2 apartados. El primero de ellos consiste en comprobar si una palabra es aceptada por un cierto autómata probabilístico, el cual es leido de unos ficheros según se indicará más adelante. Para comprobarlo se utiliza el algoritmo utilizado en clase, se coge el vector inicial, y se va multiplicando por las matrices correspondientes según los símbolos de la palabra que hay que comprobar si se acepta o no.
	
	El segundo apartado consiste en leer un autómata finito determinista, y transformarlo en un autómata finito probabilístico. Para ello se lee de varios ficheros la función de transición del AFD, y se van sacando todos los datos necesarios para tener un autómata probabilístico. Es decir, se obtienen las entradas, los estados, las matrices, el vector inicial y los estados finales.

Estructuras de Datos:

	Hemos desarrollado 4 estructuras de datos para almacenar los distintos elementos del autómata finito probabilístico. Éstas son las siguientes:

Lista de entradas: Tenemos hecha una lista dinámica, y cada nodo tiene como elemento un entero. En esta lista se van insertando todas las entradas del AFP.
Lista de estados: Es también una lista dinámica, pero los elementos de cada nodo son caracteres. En esta lista se van insertando el conjunto de estados del AFP.
Lista de estados finales: Al igual que la anterior, es una lista dinámica con caracteres como tipo elemento de los nodos. Se insertan los estados finales del AFP.
Lista de matrices: Esta estructura es una lista dinámica, y en cada nodo el tipo elemento es una tabla estática de 10x10 elementos. En esta lista se van guardando todas las matrices que corresponden a las entradas del autómata.

Las tres primeras listas se han realizado para no desaprovechar memoria, solo se utiliza la memoria necesaria para almacenar los datos. Además para el número de entradas no existe un líimite definido, no así para los estados, que el límite es 10. Por esa razón la cuarta lista realizada tiene como elemento base unas tablas de 10x10, que es el tamaño máximo de las matrices. Con esta solución se reduce la complejidad que supondría tener una lista, que tuviera como elemento base una lista de listas.

Lectura de ficheros:
	
	En todos los ficheros la lectura se realiza con un dato por línea.

Para la lectura del AFP:

Fichero entradas.txt:

El primer dato que se lee, es el número de entradas. Y los demás datos son las entradas, las cuales deben ser enteros.

Fichero estados.txt:

El primer dato es el número de estados, y después se leen los estados, los cuales deben ser siempre un carácter.

Fichero finales.txt:

Al igual que el fichero estados.txt, se lee primero el número de estados finales y después se leen dichos estados, que deben ser un carácter.

Fichero matrices.txt:

Este fichero contiene las matrices correspondientes a las entradas en el mismo orden en el que se colocaron en el fichero entradas.txt. Las matrices se colocan en orden creciente de columnas y luego de filas, es decir se inserta la primera fila de la matriz, luego la segunda, ...
Los valores de las matrices pueden ser enteros o reales. Se da por supuesto que la suma de los valores de una misma fila es 1.

Fichero inicial.txt:

Contiene los valores de cada estado para el vector inicial del AFP. Al igual que antes se presupone que la suma de todos los valores del vector es 1. Y los valores del vector al igual que antes pueden ser enteros o reales.

Para la lectura del AFD:

Fichero afd.txt:

El primer dato de este fichero es el número de estados. El segundo valor es el número de entradas. Y después de esto se introduce la matriz que corresponde a la función de transición del AFD, comenzando por la fila 1 y la columna 2, y a continuación se van insertando todas las filas como en el fichero matrices.txt.

Fichero afdinfin.txt:

El primer dato es el estado inicial del AFD. El siguiente dato a leer es el número de estados finales, y lo siguiente son dichos estados finales.

Funcionamiento del programa:
	
	Nada más comenzar el programa, lo primero que hace es cargar el AFP de los ficheros correspondientes. Después muestra en pantalla el menú principal, que consta de tres apartados, que son:

1.- Aceptar una palabra: En este apartado se parte del AFP leido de los ficheros, o del AFP obtenido a partir del AFD del apartado 2. En este apartado se comprueba a partir de ese autómata, y a partir de un umbral, solicitado al usuario si una determinada palabra introducida por teclado es aceptada por ese AFP.

2.- Pasar de AFD a AFP: Se lee el AFD de los fichero y se va transformando en el AFP correspondiente. Se va mostrando en pantalla el resultado. El AFP resultante se podrá utilizar en el apartado 1 para comprobar si cierta palabra es aceptada por él.

3.- En este apartado se carga el AFP inicial de los ficheros correspondientes para poder utilizarlo en el apartado 1. 

Datos de prueba:

EJEMPLOS DE AFP:

	Ejemplo 1:

AFP= ({0,1}, {a, b, c}, M, (0.3, 0.3, 0.4), {c})

		( 0.3   0.3   0.4)			( 0.5   0.5   0 )
	M(0)=	( 0.5   0      0.5)		M(1)= ( 0.3   0.7   0 )
		( 0      1      0   )			( 0      0      1 )

Acepta la palabra 10:

(0.3, 0.3, 0.4) x M(1) x M(0) = (

	Ejemplo 2:

AFP= ({0,1,2}, {a, b, c}, M, (1 , 0, 0), {c})

		( 1    0    0 )			( 1    0   0 )		 ( 0   1   0 )
M(0)=	( 0    0    1 )	 	M(1)= ( 0    1   0 )	M(2)=  ( 1   0   0 )
		( 0    1    0 )			( 0    0   1 )		 ( 0   0   1 )

	Ejemplo 3:

AFP= ({0, 1, 2, 3, 4}, {a, b, c, d, e}, M, (0, 0.5, 0, 0, 0.5), {b, c, e})

		( 0.6  0.3  0.1  0      0    )  
		( 0.5  0     0.3  0.2   0    )		
M(0)=	( 0.3  0.2  0.2  0.2   0.1 )	 	
		( 0.4  0.3  0.2  0.1   0    )		
		( 0.2  0.5  0     0.3   0    )

		( 0     0.3  0.5  0      0.2 )  
		( 0     0.2  0.3  0.5   0    )		
M(1)=	( 0.3  0     0     0      0.7 )	 	
		( 0.4  0     0     0.5   0.1 )		
		( 0     0     0     0      1    )

		( 0     0.4  0.5  0      0.1 )  
		( 0     0     0.8  0.2   0    )		
M(2)=	( 0.7  0.2  0.1  0      0    )	 	
		( 0     0     0     0      1    )		
		( 0     0.4  0     0.3   0.3 )

		( 1     0     0     0      0   )  
		( 0     1     0     0      0   )		
M(3)=	( 0     0     1     0      0   )	 	
		( 0     0     0     1      0   )		
		( 0     0     0     0      1   )

		( 0.9  0     0.1  0      0   )  
		( 0.1  0     0.6  0.3   0   )		
M(4)=	( 0.4  0.2  0.2  0.2   0   )	 	
		( 0.4  0.3  0.2  0.1   0   )		
		( 0.6  0    0     0.4   0   )

EJEMPLOS DE AFD:

	Ejemplo 1:

f
0
1
2

->a
d
d
e

b
c
d
e

c
c
c
c

*d
d
d
e

*e
d
b
e

	Ejemplo 2:

f
0
1

->q
q
p

r
r
p

*p
p
r

3º I. T. Informática de Sistemas		Diego Chaparro González
Universidad Rey Juan Carlos		Daniel Rubio Castillo

PRÁCTICA DE AUTÓMATAS	
Práctica 11: Autómatas Probabilísticos		Página 6 de