Description

Grado en Ingeniería Informática
Práctica 1 (autómatas finitos)
1. Implemente una función es_afne : Auto.af -> bool que reciba como argumento un autómata finito, y que devuelva true si se trata de un autómata que presenta alguna épsilon-transición, o false en caso contrario.
Implemente una función es_afn : Auto.af -> bool que reciba como argumento un autómata finito, y que devuelva true si se trata de un autómata que presenta algún tipo de no determinismo (excepto épsilon-transiciones), o false en caso contrario.
Implemente una función es_afd : Auto.af -> bool que reciba como argumento un autómata finito, y que devuelva true si se trata de un autómata totalmente determinista, o false en caso contrario.
2. Implemente una función equivalentes : Auto.af -> Auto.af -> bool que reciba como argumentos dos autómatas finitos y que devuelva true cuando ambos autómatas acepten el mismo lenguaje, o false en caso contrario.
3. [Ejercicio opcional] La librería ocaml_talf proporciona la función escaner_af :
Auto.simbolo list -> Auto.af -> bool, que dada una lista de símbolos terminales y un
autómata finito indica si dicha cadena de símbolos es aceptada o no por el autómata. Se trata de una versión de la función de reconocimiento más general posible, es decir, aquélla que es capaz de simular el funcionamiento de cualquier tipo de autómata finito (determinista, no determinista, e incluso no determinista con épsilon-transiciones).
Reimplemente la función anterior para definir ahora una función escaner_afn : Auto.simbolo list -> Auto.af -> bool, que dada una lista de símbolos terminales y un autómata finito indica si dicha cadena de símbolos es aceptada o no por el autómata. Se trata de una versión de la función de reconocimiento que es capaz de simular de manera más óptima el funcionamiento de autómatas finitos con cualquier tipo de no determinismo (excepto épsilon-transiciones).
Reimplemente la función anterior para definir ahora una función escaner_afd : Auto.simbolo list -> Auto.af -> bool, que dada una lista de símbolos terminales y un autómata finito indica si dicha cadena de símbolos es aceptada o no por el autómata. Se trata de una versión de la función de reconocimiento que es capaz de simular de manera todavía más óptima el funcionamiento de autómatas finitos totalmente deterministas.