Implementació d’una eina docent per a l’assignatura de Fonaments de la Computació

Abstract

En aquest projecte es pretén desenvolupar una eina docent que doni suport tant a estudiants com a docents d’assignatures relacionades amb la teoria de la computació. Els problemes de llenguatges, gramàtiques i autòmats admeten solucions molt diverses. Això fa que els estudiants sovint tinguin dubtes de si la seva solució ´es correcta encara que s’hagi publicat una possible solució. També per als professors pot fer-se carregós corregir determinats exercicis, davant la diversitat de respostes possibles. Els objectius del projecte son: La conversió d’autòmats finits en expressions regulars i viceversa. - La determinació de l’equivalència d’expressions regulars. - La determinació de l’equivalència de gramàtiques i la cerca de contraexemples. - La determinació de l’ambigüitat de gramàtiques. Els dos últims objectius plantejats son problemes indecidibles. És a dir, no existeix un algorisme que els pugui resoldre. Per tant, es pretén buscar informació de com resoldre aquests problemes i estudiar diverses opcions disponibles. Altres funcionalitats per afegir al projecte son: - La generació de paraules a partir d’expressions, gramàtiques i autòmats. - L’acceptació de paraules a partir d’expressions, gramàtiques i autòmats. - La simplificació de gramàtiques. - La transformació de gramàtiques a formes normals. Per dur a terme totes aquestes tasques s’ha de determinar un format d’entrada pels autòmats, expressions i gramàtiques. Així doncs, l’aplicació ha de permetre llegir fitxers en aquests formats i mostrar el resultat de l’execució també en aquests formats.

4