Models abstractes de representació de llenguatges regulars

Índex 1 Introducció 7 1.1 Origendelprojecte................................ 7 1.2 Objectius generals del projecte . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Avaluació d’alternatives i solució triada . . . . . . . . . . . . . . . . . . . . . 8 2 Resum de la teoria d’autòmats 9 2.1 Símbols,motsialfabets ............................. 9 2.2 Llenguatgesformals................................ 10 2.3 Autòmatsfinits .................................. 10 2.3.1 Autòmat finit determinista o DFA . . . . . . . . . . . . . . . . . . . . 10 2.3.2 Autòmat finit indeterminista o NFA . . . . . . . . . . . . . . . . . . . 12 2.3.3 Autòmat finit indeterminista amb l -transicions o l -NFA . . . . . . . 14 2.4 Expressionsregulars ............................... 15 3 Definició del projecte 17 3.1 Context ...................................... 17 3.2 Requisits funcionals i no funcionals . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.1 Requisits funcionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1 3.2.2 Requisits no funcionals . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3 Planificaciótemporal............................... 21 3.4 Previsiódecost.................................. 23 3.4.1 Recursoshumans............................. 23 3.4.2 Llicències del programari . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4.3 Recursos de maquinari . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4.4 Total.................................... 25 3.5 Objectiusdelprojecte .............................. 26 4 Especificació 27 4.1 Modeldecasosd’ús................................ 27 4.1.1 Descripció dels actors que intervenen en el sistema . . . . . . . . . . . 27 4.1.2 Diagrama de casos d’ús . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.1.3 Especificació de casos d’ús . . . . . . . . . . . . . . . . . . . . . . . . 28 4.1.3.1 Especificació de casos d’ús de DFA . . . . . . . . . . . . . . 28 4.1.3.2 Especificació de casos d’ús de NFA . . . . . . . . . . . . . . 38 4.1.3.3 Especificació de casos d’ús de l -NFA............. 47 4.1.3.4 Especificació de casos d’ús d’expressions regulars . . . . . . 55 4.2 Modelconceptual................................. 59 4.3 Contracte de les operacions . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.1 Conctracte de les operacions de DFA . . . . . . . . . . . . . . . . . . 61 4.3.2 Conctracte de les operacions de NFA . . . . . . . . . . . . . . . . . . 65 4.3.3 Conctracte de les operacions de l -NFA................. 69 4.3.4 Conctracte de les operacions d’expressions regulars . . . . . . . . . . 72 2 5 Disseny 75 5.1 Arquitectura general del sistema . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.2 CapadePresentació ............................... 77 5.2.1 Funcions de la capa de presentació . . . . . . . . . . . . . . . . . . . 77 5.2.2 Disseny de la capa de presentació . . . . . . . . . . . . . . . . . . . . 77 5.2.2.1 Disseny i composició de les diferents vistes. . . . . . . . . . 78 5.2.2.2 Vista principal . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.2.2.3 Vista de consulta . . . . . . . . . . . . . . . . . . . . . . . . 80 5.2.2.4 Vista d’assistents . . . . . . . . . . . . . . . . . . . . . . . . 82 5.3 CapadelDomini ................................. 83 5.3.1 Funcions de la capa del Domini . . . . . . . . . . . . . . . . . . . . . 83 5.3.2 Disseny de la capa del Domini . . . . . . . . . . . . . . . . . . . . . . 84 5.4 Capadegestiódedades ............................. 84 5.4.1 Funcions de la capa de gestió de dades . . . . . . . . . . . . . . . . . 84 5.4.2 Disseny de la capa de gestió de dades . . . . . . . . . . . . . . . . . . 85 6 Implementació 87 6.1 Tecnologiesaferservir.............................. 87 6.2 Entorn de desenvolupament . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.3 Diagramadeclasses................................ 88 6.4 Arquitectura en tres capes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.5 Gestiód’errors .................................. 90 3 7 Proves 91 7.1 Provesdetallades ................................. 91 7.1.1 Prova de minimització d’un DFA . . . . . . . . . . . . . . . . . . . . 92 7.1.2 Prova de supressió de l -transicions d’un l -NFA ............ 96 7.1.3 Prova de determinització d’un NFA . . . . . . . . . . . . . . . . . . . 98 7.1.4 Prova d’obtenció d’un autòmat a partir d’una expressió regular . . . 100 8 Revisió de la planificació 105 8.1 Desenvolupament temporal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 8.2 Costdelprojecte ................................. 108 9 Conclusions 111 9.1 Implantacióiavaluació.............................. 111 9.2 Objectiusassolits................................. 111 9.3 Possibles ampliacions i millores . . . . . . . . . . . . . . . . . . . . . . . . . 112 9.4 Conclusionspersonals............................... 113 4 Glossari de termes •ALCC: ALgorísmia, Calculabilitat i Complexitat •Alfabet: conjunt de símbols. •DFA: Autòmat finit determinista, de l’anglès deterministic finite automaton. •ER: Expressió regular •F: conjunt d’estats finals d’un autòmat •I: conjunt d’estats inicials d’un autòmat •Llenguatge: conjunt de mots sobre un alfabet. •Mot: concatenació de símbols que formen una cadena. •NFA: Autòmat finit indeterminista, de l’anglès nondeterministic finite automaton. •PFC: projecte final de carrera •Q: conjunt d’estats. •Símbol: Element d’un alfabet. •Σ: alfabet •δ: funció de transició d’un autòmat. •λ: mot buit. • l -NFA: Autòmat finit indeterminista amb l -transicions, de l’anglès nondeterministic finite automaton with l -transitions. 5 6 Capítol 1 Introducció 1.1 Origen del projecte L’origen d’aquest projecte se situa poc abans d’acabar l’any 2009, després d’aproximadament mig any respecte la data de finalització de totes les assigunatures de la titulació. Durant aquest temps entre la finalització de les assignatures i l’inici d’aquest projecte, s’aprofita per obrir un període de reflexió i intentar obtenir una visió global i des de la distància del que ha sigut tot aquest llarg camí d’assignatures. Preguntant-se si ha complert les expectatives creades en el seu inici, quins han sigut els punts forts, quins els dèbils, amb quins s’ha gaudit més i amb quins menys. Tot això enfocat de cara a l’elecció de temàtica del PFC (projecte final carrera), doncs estava clar que si s’havia de fer tot un PFC, s’havia de fer d’algun tema que realment agradés i motivés, doncs de no ser així, fer el PFC es faria molt complicat. I el resultat d’aquesta reflexió va ser ALCC (ALgorísmia, Calculabilitat i Complexitat) , nom d’una de les últimes assignatures cursades. Així doncs, un cop arribats a aquesta conclusió, es va procedir a la cerca d’un PFC que tractés algun dels temes estudiats en aquesta assignatura. Al no trobar a la secció de PFC proposats de la pàgina web de la facultat cap projecte referent a aquesta assignatura, es decideix contactar directament amb el professor i responsable de l’assignatura d’ALCC, i tutor d’aquest PFC, Antoni Lozano Bojadós, per tractar el tema de la realització d’un PFC referent a l’àmbit d’estudi d’ALCC. Finalment s’arriba a un acord entre alumne i professor pel qual es realitza un PFC on l’alumne pot ampliar una part dels coneixements adquirits a ALCC i per altra es realitza una aplicació que pot arribar a tenir una funcionalitat didàctica per qualsevol persona interessada en temes d’estudi d’aquest àmbit. 7 1.2 Objectius generals del projecte Aquest projecte té dos grans objectius molt clars i diferenciats. Per una banda, i sobretot des del punt de vista de l’estudiant, l’objectiu és ampliar els coneixements introduïts a ALCC. El bon regust de boca deixat per l’assignatura, la curiositat i les ganes de seguir aprenent justifiquen aquest punt. Aquest és el motiu principal que mou l’estudiant a fer el seu PFC sobre aquesta temàtica. L’altre gran objectiu d’aquest projecte és la realització d’una aplicació que permeti operar i simular el funcionament d’algunes de les formes de representació dels llenguatges formals. Algunes d’aquestes representacions van ser introduïdes a l’assignatura d’ALCC, d’altres s’han aprés com a objectiu del projecte. Aquesta aplicació és pensada des del seu inici com una aplicació que pugui ser usada com a eina per qualsevol persona interessada en l’estudi de temes d’aquest àmbit. 1.3 Avaluació d’alternatives i solució triada Un cop alumne i tutor tenen una idea sobre què ha de contenir el projecte, el primer que es fa és una cerca i avaluació de les diferents opcions ja existents. Algunes de les alternatives estudiades són Visual Automata Simulator [1], jFast [2], jFlap [3] i Reanimator [4]. Tot i que algunes d’aquestes opcions existents ofereixen solucions molt interessants a determinats problemes, es decideix que val la pena el desenvolupament d’una nova aplicació, doncs certs aspectes com ara les operacions entre autòmats són inexistents, o tractades superficialment en les opcions existents. 8 Capítol 2 Resum de la teoria d’autòmats En aquest capítol es pretèn fer una breu introducció o un petit recordatori dels aspectes de la teoria d’autòmats tractats en aquest PFC. 2.1 Símbols, mots i alfabets Un alfabet és un conjunt finit no buit, els elements del qual s’anomenen símbols. Un exemple d’alfabet és l’alfabet català que és un cojunt finit no buit de 28 símbols {A, ... ,Z}. Altres exemples d’alfabets poden ser l’alfabet decimal {0, ... ,9} o l’alfabet binari {0,1}. Normalment es fa servir la lletra grega S per referirse a un alfabet. A partir d’un alfabet es pot definir el que és un mot. Donat un alfabet qualsevol, un mot és una seqüència finita de símbols concatenats d’aquest alfabet. La longitud d’un mot ve indicada pel nombre de símbols que té el mot. Als mots de longitud zero se’ls anomena mots buits i es representen amb l . Així, sobre l’alfabet de la llengua catalana tenim que ’casa’ és un mot, ’aaaa’ és un mot, ” és un mot (mot buit) i ’peeface’ també és un mot. En canvi, sobre aquest alfabet català, ’caña’ no és un mot, doncs el símbol ’ñ’ no pertany a l’alfabet català. Es representa per Σ∗el conjunt infinit de tots els mots possibles sobre un cert alfabet Σ. Com que el mot l és un dels mots definits en qualsevol alfabet es pot afirmar que és un mot que sempre formarà part de Σ∗. Per exemple, sobre l’alfabet binari Σ = {0,1}es té que Σ∗={λ, 0,1,10,11,110,111, ..., 110011, ...}el conjunt de tots els mots que es poden formar sobre Σ. 9 1. Λi∅són expressions regulars. 2. Per a cada símbol ade Σ,aés una expressió regular. 3. Si r1ir2són expressions regulars, també ho són (r1+r2) i (r1·r2). 4. Si rés una expressió regular, també ho és (r∗). 5. Totes les expressions regulars sobre Σs’obtenen aplicant 1, 2, 3 i 4. I també definirem el llenguatge associat a una expressió regular rel llenguatge L(r)definit recursivament així: 1. {λ},∅o{a}, si rés ∆,∅oa, respectivament. 2. L(r1)∪L(r2)oL(r1)·L(r2), si r= (r1+r2)or= (r1·r2), respectivament. 3. (L(r1))∗si r= (r∗ 1). Els llenguatges que reconeixen les expressions regulars són també llenguatges regulars i per tant tenen un autòmat associat. Com en la secció anterior, no entrarem a demostrar l’afirmació anterior. Es pot trobar a [5]. Les expressions regulars faciliten molt la descripció de llenguatges regulars. Són molt visuals i poden arribar a ser molt compactes oferint una definició del llenguatge que reconeixen amb molt poc espai i molta claredat. Per exemple suposem l’alfabet Σ = {a.b, c}. El llenguatge Σ∗és descrit per l’expressió regular (a+b+c)∗. 16 Capítol 3 Definició del projecte 3.1 Context A diferència d’altres aplicacions més genèriques o d’un ús més general, la desenvolupada en aquest PFC tracta sobre certs aspectes molt concrets de la teoria de la computació. Això fa que el segment d’usuaris a qui va dirigida l’aplicació sigui molt concret. Per exemple, per una persona que no estigui familiaritzada en temes com la teoria d’autòmats, l’aplicació aquí desenvolupada pot resultar de dubtosa utilitat. Com a conseqüència de tot això, es pot situar l’aplicació en un context acadèmic, on l’objectiu principal sigui reforçar l’aprenentatge proporcionant una eina per la validació de resultats i per la lliure experimentació. Referent a l’aplicació en si, es preten que l’aplicació funcioni a mode de simulador de models de representació de llenguatges formals, i que permeti una sèrie d’operacions i transformacions entre alguns dels models tractats. 3.2 Requisits funcionals i no funcionals En aquest apartat analitzarem els requisits tant funcionals com no funcionals necessaris per l’aplicació desenvolupada per realitzar aquest projecte. 17 Aquests requisits s’han elaborat mitjançant les necessitats reportades pels usuaris finals de l’aplicació (tutor i alumne) adaptant-se a les seves necessitats, però sense oblidar les limitacions tècniques, pressupostàries o temporals. A continuació s’exposen d’una forma detallada els requisits funcionals i els requisits no funcionals considerats a l’hora de desenvolupar l’aplicació. 3.2.1 Requisits funcionals Són aquells que defineixen el funcionament o funcionalitats proporcionades pel sistema i realitzats pel programari. •L’aplicació ha de ser capaç d’operar amb les següents formes de models de càlcul: Autòmats finits deterministes (DFA), autòmats finits indeterministes (NFA), autòmats finits indeterministes amb l -transicions ( l -NFA) i expressions regulars. •L’aplicació ha de permetre crear noves instàncies de DFA, NFA, l -NFA i expressions regulars. •L’aplicació ha de permetre a l’usuari la creació de zero, una o més d’una instància de DFA, NFA, l -NFA i expressions regulars en una execució. •L’aplicació ha de permetre a l’usuari l’eliminació d’una instància. •L’aplicació ha de mostrar a l’usuari totes les instàncies creades. •L’aplicació ha de permetre consultar els atributs que defineixen a una instància d’aquests models de càlcul. En concret: –En el cas de DFA, NFA i l -NFA aquests atributs són el conjunt d’estats, el conjunt de símbols de l’alfabet, la funció de transició, el conjunt d’estats inicials i el conjunt d’estats finals. –En el cas d’expressions regulars aquests atributs són la pròpia expressió regular i l’alfabet sobre el qual està definida. •A partir d’un DFA, NFA o l -NFA el programa ha de generar una imatge que, mitjançant un graf dirigit i seguint la notació habitual, representi de forma visual qualsevol d’aquests tres tipus d’autòmat. 18 •L’aplicació ha de permetre un seguit de conversions entre formes de models de càlcul. El resultat d’una operació sobre un tipus d’autòmat que retorni un tipus d’autòmat diferent a l’orginal o una expressió regular, no s’entén com a conversió. En concret: –Conversió de expressió regular a l -NFA. –Conversió de l -NFA a NFA. –Conversió de NFA a DFA. •Particularment i per a cada model de càlcul l’aplicació ha de permetre un seguit d’operacions: –DFA ∗Donat un DFA, obtenir un nou DFA que sigui la minimització d’aquest DFA. ∗Donat un DFA i un mot, determinar si el DFA reconeix el mot. ∗Donat un DFA, obtenir un nou DFA que sigui la complementació d’aquest DFA. ∗Donats dos DFA, obtenir un nou DFA que sigui la intersecció d’aquests dos DFA. ∗Donats dos DFA, obtenir un nou DFA que sigui la reunió d’aquests dos DFA. ∗Donats dos DFA, obtenir un nou l -NFA que sigui la concatenació d’aquests dos DFA. ∗Donat un DFA, obtenir un nou l -NFA que sigui el tancament positiu d’aquest DFA. ∗Donat un DFA, obtenir un nou l -NFA que sigui el tancament de Kleene d’aquest DFA. –NFA ∗Donat un NFA i un mot, determinar si el NFA reconeix el mot. ∗Donats dos NFA, obtenir un nou NFA que sigui la intersecció d’aquests dos NFA. ∗Donats dos NFA, obtenir un nou NFA que sigui la reunió d’aquests dos NFA. ∗Donats dos NFA, obtenir un nou NFA que sigui la concatenació d’aquests dos NFA. ∗Donat un NFA, obtenir un nou l -NFA que sigui el tancament positiu d’aquest NFA. 19 ∗Donat un NFA, obtenir un nou l -NFA que sigui el tancament de Kleene d’aquest NFA. – l -NFA ∗Donat un l -NFA i un mot, determinar si el l -NFA reconeix el mot. ∗Donats dos l -NFA, obtenir un nou l -NFA que sigui la reunió d’aquests dos l -NFA. ∗Donats dos l -NFA, obtenir un nou l -NFA que sigui la concatenació d’aquests dos l -NFA. ∗Donat un l -NFA, obtenir un nou l -NFA que sigui el tancament positiu d’aquest l -NFA. ∗Donat un l -NFA, obtenir un nou l -NFA que sigui el tancament de Kleene d’aquest l -NFA. –Expressions regulars ∗Donada una expressió regular i un mot, determinar si l’expressió regular reconeix el mot. 3.2.2 Requisits no funcionals Són aquells que especifiquen aquells aspectes desitjats del sistema que no es corresponen a funcionalitats o accions a realitzar per l’usuari. Tot seguit s’enumeren: •Usabilitat. De cara a l’usuari, és molt important que l’aplicació sigui fàcil de fer servir, intuïtiva, i que no requereixi de coneixements específics sobre l’aplicació per a fer-ne ús. Com més intuitiva i agradable a la vista, més còmode es sentirà l’usuari i més futur tindrà l’aplicació. •Multi plataforma. És clar que si disposem d’una aplicació multi plataforma, potencialment es poden tenir molts més usuaris. Al mateix temps tots els usuaris de les diferents plataformes estaran igual de satisfets per la disponibilitat de l’aplicació pel seu sistema. Les plataformes per les que ha estat pensada l’aplicació són: MacOS, Linux i Windows. •Portable: No és un requisit indispensable, pero el fet de que l’aplicació sigui totalment portable i que no requereixi d’instal·lació per el seu ús, facilita la seva distribució. 20 •Oberta: Compartint el codi de l’aplicació es permet que altres persones interessades en aquest projecte puguin veure com està fet, o inclús fer-hi millores o personalitzacions el seu gust. •Ús de programari lliure. Desenvolupar tota l’aplicació mitjançant programari lliure permet reduir els costos de producció de l’aplicació. •Ajudes i errors. L’aplicació ha d’avisar a l’usuari de possibles errors i proporcionar-li ajuda. 3.3 Planificació temporal En aquest apartat es mostra la planificació de tot el projecte que es va fer a l’inici. Més endavant, en l’apartat corresponent, s’exposarà la planificació final feta a l’acabar el projecte i es comentaran les diferències. La planificació i els requisits de l’aplicació es planifiquen en base a la guia docent de la facultat on s’especifica que el projecte per l’Enginyeria Tècnica en Informàtica de Sistemes té un pes de 22,5 crèdits, i s’estima que cada crèdit té una càrrega de treball per l’estudiant de 20 hores. Donant una previsió de 450 hores . Pel que fa a la distribució d’aquestes hores en el temps, també es basa en la guia docent de la facultat, on s’aproxima que un projecte de l’Enginyeria Tècnica de Sistemes es pot realitzar durant un quadrimestre amb una dedicació de mitja jornada (20 hores a la setmana). A continuació es mostra en format de diagrama de Gantt la planificació inicial: 21 Figura 3.1: Diagrama de Gantt inicial Tot seguit es pot veure en detall les hores planificades per a cada punt. 22 Secció Hores Definició del projecte Descripció del projecte 10 Anàlisi opcions existents 5 Anàlisi de requisits 10 Planificació 5 Pressupost 3 Formació específica Formació 20 Especificació Especificació 20 Disseny Búsqueda solucions 5 Selecció plataforma 2 Disseny 40 Implementació Implementació 200 Proves 20 Documentació Memòria 100 Presentació 10 TOTAL 450 Taula 3.1: Taula resum d’hores 3.4 Previsió de cost En aquest apartat es detalla en base a la planificació temporal inicial, una previsió de costos per l’execució de tot el projecte. Per obtenir l’anàlisi completa de costos del projecte s’han de tenir en compte els recursos humans que s’han fet servir, les llicències del programari usat, i els recursos de maquinari. 3.4.1 Recursos humans Primer de tot cal diferenciar els diferents rols que intervenen durant tot el procés de realització del projecte. S’enumeren a continuació. 23 •Director de projecte: S’encarrega de la supervisió de totes les tasques a realitzar, a fer un seguiment d’objectius de l’avanç del projecte i es reuneix amb el client (tutor) per a la presa de decisions. •Analista: Es reuneix amb el client (tutor) per conèixer les seves necessitats i elabora la documentació sobre requisits, especificacions i disseny del projecte. •Programador: S’encarrega de transformar les especificacions del projecte al producte final que serà entregat al client (tutor). Les tasques a desenvolupar durant el projecte són les següents. •Anàlisi de requisits: Comprèn les entrevistes amb el tutor del projecte i l’elaboració dels requisits de l’aplicació. •Especificació: Consisteix en descriure de forma detallada totes les característiques i funcionalitats que tindrà el programa. •Disseny: Consisteix en definir l’estructura que tindrà el programa, realitzar l’especificació de totes les parts i decidir la tecnologia que s’usarà en el desenvolupament. •Implementació: Consisteix, com el seu nom indica, en la implementació del projecte en la tecnologia escollida en la fase de disseny. •Gestió del projecte: Seguiment de l’evolució del projecte en les diferents fases, reunions amb el tutor i realització de les tasques de gestió (previsió de cost, planificació temporal, elaboració de la memòria, etc.). •Proves: Consisteix en realitzar les proves de funcionament de l’aplicació un cop acabada la implementació. •Formació: Donada la temàtica del projecte, s’ha hagut de dedicar un cert temps a fer formació específica sobre els temes que tracta aquest projecte. •Documentació: Consisteix en l’elaboració de la documentació que es lliurarà. A partir d’aquesta informació s’elabora la taula següent 24 Tasca Rol Hores Preu per hora (€) Cost (€) Anàlisi de requisits Analista 10 35 350 Especificació Analista 20 35 700 Disseny Analista 47 35 1645 Implementació Programador 200 20 4000 Gestió del projecte Director de projecte 23 60 1380 Proves Programador 20 20 400 Formació Programador 20 20 400 Documentació Analista 110 35 3850 TOTAL 450 12725 Taula 3.2: Taula de costos de recursos humans 3.4.2 Llicències del programari Tot el programari que s’ha fet servir durant el desenvolupament de l’aplicació ha sigut gratuït i de codi obert. Concretament el sistema operatiu fet servir al llarg de tot el projecte ha sigut Linux/Ubuntu, la implementació s’ha fet sobre Java fent servir l’IDE Netbeans i la memòria del projecte s’ha fet mitjançant L A TEX. 3.4.3 Recursos de maquinari S’ha necessitat d’un ordinador personal per a la realització de l’aplicació. S’hauria d’incloure aquí el cost del desgast dels components de l’ordinador fet servir, però es desestimen donat el seu import molt baix comparativament al cost global del projecte. 3.4.4 Total Donat que el cost de les llicències del programari i el de recursos de maquinari és zero, la suma total de la previsió de costos del projecte és de 12.725 €, tenint en compte que es dediquen 450 hores. Veure taula 3.3 25 Tipus: Primari i essencial. Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1. Selecciona un DFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó de “Minimitzar DFA” 4. Apareix un assistent 5. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de la minimització. 6. Es crea el nou DFA Taula 4.5: Minimitzar DFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Complementar DFA. Actors: Usuari. Propòsit: Donat un DFA qualsevol, obtenir el seu DFA complementat. Resum: A partir d’un DFA qualsevol, i mitjançant un assistent que guiarà a l’usuari durant tot el procés, obtenir el DFA complementat. Tipus: Primari i essencial. Curs típic d’esdeveniments: 32 Accions de l’actor Resposta del sistema 1. Selecciona un DFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó d’ “Operacions” 4. Mostra un assistent 5. Selecciona “Complementar”. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de la complementació. 6. Es crea el nou DFA Taula 4.6: Complementar DFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Reunió DFA. Actors: Usuari. Propòsit: A partir de dos DFA, obtenir el DFA resultant de fer la reunió d’aquests dos. Resum: A partir d’un DFA qualsevol i des de la vista de consulta, s’accedeix a l’assistent d’operacions que proposarà a l’usuari una selecció de DFA amb el mateix alfabet que l’original, perquè aquest en triï un i finalment obtenir així el DFA reunió. Tipus: Primari i essencial. Curs típic d’esdeveniments: 33 Accions de l’actor Resposta del sistema 1. Selecciona un DFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó d’ “Operacions” 4. Mostra un assistent 5. Selecciona “Reunió”. 6. Selecciona amb quin DFA dels proposats vol fer la reunió 7. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de la reunió. 8. Es crea el nou DFA Taula 4.7: Reunió DFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Intersecció DFA. Actors: Usuari. Propòsit: A partir de dos DFA, obtenir el DFA resultant de fer la intersecció d’aquests dos. Resum: A partir d’un DFA qualsevol i des de la vista de consulta, s’accedeix a l’assistent d’operacions que proposarà a l’usuari una selecció de DFA amb el mateix alfabet que l’original, per a que aquest en triï un i finalment obtenir aixi el DFA intersecció. Tipus: Primari i essencial. Curs típic d’esdeveniments: 34 Accions de l’actor Resposta del sistema 1. Selecciona un DFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó d’ “Operacions” 4. Mostra un assistent 5. Selecciona “Intersecció” 6. Selecciona amb quin DFA dels proposats vol fer la intersecció 7. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de la intersecció. 8. Es crea el nou DFA Taula 4.8: Intersecció DFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Concatenació DFA. Actors: Usuari. Propòsit: A partir de dos DFA, obtenir el l -NFA resultant de fer la concatenació d’aquests dos. Resum: A partir d’un DFA qualsevol i des de la vista de consulta, s’accedeix a l’assistent d’operacions que proposarà a l’usuari una selecció de DFA amb el mateix alfabet que l’original, per a que aquest en trii un i finalment obtenir aixi el l -NFA concatenació. Tipus: Primari i essencial. Curs típic d’esdeveniments: 35 Accions de l’actor Resposta del sistema 1. Selecciona un DFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó de Operacions 4. Mostra un assistent 5. Selecciona “Concatenació” 6. Selecciona amb quin DFA dels proposats es vol fer la concatenació 7. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de la concatenació. 8. Es crea el nou l -NFA Taula 4.9: Concatenació DFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Kleene DFA. Actors: Usuari. Propòsit: A partir d’un DFA, obtenir el l -NFA resultant de fer el tancament de Kleene d’aquest. Resum: A partir d’un DFA qualsevol i des de la vista de consulta, s’accedeix a l’assistent d’operacions, es selecciona la operació “Tancament de Kleene” i es segueix l’assistent que guiarà a l’usuari durant tot el procés per obtenir aixi el l -NFA resultant. Tipus: Primari i essencial. Curs típic d’esdeveniments: 36 Accions de l’actor Resposta del sistema 1. Selecciona un DFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó d’ “Operacions” 4. Mostra un assistent 5. Selecciona “Tancament de Kleene” 6. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de fer el tancament de Kleene. 7. Es crea el nou l -NFA Taula 4.10: Tancament de Kleene DFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Tancament Positiu DFA. Actors: Usuari. Propòsit: A partir d’un DFA, obtenir el l -NFA resultant de fer el tancament positiu d’aquest. Resum: A partir d’un DFA qualsevol i des de la vista de consulta, s’accedeix a l’assistent d’operacions, es selecciona la operació “Tancament positiu” i es segueix l’assistent que guiarà a l’usuari durant tot el procés per obtenir aixi el l -NFA resultant. Tipus: Primari i essencial. Curs típic d’esdeveniments: 37 Accions de l’actor Resposta del sistema 1. Selecciona un DFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó de Operacions 4. Mostra un assistent 5. Selecciona “Tancament Positiu” 6. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de fer el tancament positiu. 7. Es crea el nou l -NFA Taula 4.11: Tancament Positiu DFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. 4.1.3.2 Especificació de casos d’ús de NFA •Cas d’ús: Crear nou NFA. Actors: Usuari. Propòsit: Crear una nova instància de NFA. Resum: Mitjançant l’ús d’un assistent es crearà una nova instància de NFA. Tipus: Primari i essencial. Curs típic d’esdeveniments: 38 Accions de l’actor Resposta del sistema 1. Accedir a l’aplicació 2. Selecciona Arxiu >> Nou 3. Mostra l’assistent per a la creació d’una nova instància 4. Seleccionar NFA. Segons vagi avançant l’assistent anar introduint el nom, el conjunt de símbols, l’alfabet, la taula de transicions, el conjunt d’estats inicials i el conjunt d’estats finals. 5. Es crea la instància de NFA Taula 4.12: Nou_NFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Suprimir NFA. Actors: Usuari. Propòsit: Esborrar una instància de NFA. Resum: Un cop l’usuari hagi entrat a l’aplicació, hagi seleccionat alguna instància de NFA i premi el botor “Esborrar”, s’esborrarà el NFA seleccionat. Tipus: Primari i essencial. Curs típic d’esdeveniments: 39 Accions de l’actor Resposta del sistema 1. Seleccina una instància 2. Prem el botó “Esborrar” 3. S’esborra la instància seleccionada Taula 4.13: Sup_NFA Errors possibles: –S’intenta esborrar sense seleccionar cap instància. Cursos alternatius: En cas d’error l’usuari rebrà un missatge informat de que no ha seleccionat cap instància. •Cas d’ús: Consultar NFA. Actors: Usuari. Propòsit: Consultar una instància de NFA Resum: Consultar els elements que formen un NFA (nom, conjunt d’estats, alfabet, taula de transicions, estat inicial i conjunt d’estats finals). Tipus: Primari i essencial. Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1. Selecciona una instància 2. Mostra una finestra nova amb els detalls Taula 4.14: Consultar_NFA Errors possibles: - Cursos alternatius: - 40 •Cas d’ús: Reconèixer mot NFA. Actors: Usuari. Propòsit: Donat un mot i una instància de NFA, determinar si aquest mot és reconegut per la instància. Resum: Des de la finestra de consultes, apareix l’opció en format de camp de text per introduir un mot. Automàticament el programa simularà el funcionament d’aquesta instància i determinarà si el mot és reconegut o no. Tipus: Primari i essencial. Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1. Selecciona una instància 2. Mostra la finestra amb els detalls 3. En la secció corresponent de la finestra, escriu el mot que vol que sigui reconegut 4. Mostra un missatge informant del resultat Taula 4.15: Reconèixer mot NFA Errors possibles: –El mot a reconèixer sigui massa llarg Cursos alternatius: En cas d’error l’usuari rebrà un missatge informant de l’error. •Cas d’ús: Determinitzar NFA. Actors: Usuari. Propòsit: Obtenir el DFA resultant de determinitzar un NFA qualsevol. Resum: A partir d’un NFA qualsevol, i mitjançant un assistent que guiarà a l’usuari durant tot el procés, obtenir el DFA equivalent. 41 Accions de l’actor Resposta del sistema 1. Accedir a l’aplicació 2. Selecciona Arxiu >> Nou 3. Mostra l’assistent per a la creació d’una nova instància 4. Seleccionar l -NFA. Segons vagi avançant l’assistent anar introduint el nom, el conjunt de símbols, l’alfabet, la taula de transicions, el conjunt d’estats inicials i el conjunt d’estats finals. 5. Es crea la instància de l -NFA Taula 4.22: Nou_ l -NFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Suprimir l -NFA. Actors: Usuari. Propòsit: Esborrar una instància de l -NFA. Resum: Un cop l’usuari hagi entrat a l’aplicació, hagi seleccionat alguna instància de l -NFA i premi el botor “Esborrar”, s’esborrarà el l -NFA seleccionat. Tipus: Primari i essencial. Curs típic d’esdeveniments: 48 Accions de l’actor Resposta del sistema 1. Seleccina una instància 2. Prem el botó “Esborrar” 3. S’esborra la instància seleccionada Taula 4.23: Sup_ l -NFA Errors possibles: –S’intenta esborrar sense seleccionar cap instància. Cursos alternatius: En cas d’error l’usuari rebrà un missatge informat de que no ha seleccionat cap instància. •Cas d’ús: Consultar l -NFA. Actors: Usuari. Propòsit: Consultar una instància de l -NFA Resum: Consultar els elements que formen un l -NFA (nom, conjunt d’estats, alfabet, taula de transicions, estat inicial i conjunt d’estats finals). Tipus: Primari i essencial. Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1. Selecciona una instància 2. Mostra una finestra nova amb els detalls Taula 4.24: Consultar_ l -NFA Errors possibles: - Cursos alternatius: - 49 •Cas d’ús: Reconèixer mot l -NFA. Actors: Usuari. Propòsit: Donat un mot i una instància de l -NFA, determinar si aquest mot és reconegut per la instància. Resum: Des de la finestra de consultes, apareix l’opció en format de camp de text per introduir un mot. Automàticament el programa simularà el funcionament d’aquesta instància i determinarà si el mot és reconegut o no. Tipus: Primari i essencial. Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1. Selecciona una instància 2. Mostra la finestra amb els detalls 3. En la secció corresponent de la finestra, escriu el mot que vol que sigui reconegut 4. Mostra un missatge informant del resultat Taula 4.25: Reconèixer mot l -NFA Errors possibles: –El mot a reconèixer sigui massa llarg Cursos alternatius: En cas d’error l’usuari rebrà un missatge informant de l’error. •Cas d’ús: l -NFA a NFA. Actors: Usuari. Propòsit: Obtenir el NFA resultant d’eliminar les l -transicions d’un l -NFA qualsevol. Resum: A partir d’un l -NFA qualsevol, i mitjançant un assistent que guiarà a l’usuari durant tot el procés, obtenir el NFA equivalent. 50 Tipus: Primari i essencial. Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1.Selecciona un l -NFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó de “to NFA” 4. Mostra un assistent 5. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de fer la transformació de l -NFA a NFA. 6. Es crea el nou NFA Taula 4.26: l -NFA a NFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Reunió l -NFA. Actors: Usuari. Propòsit: A partir de dos l -NFA, obtenir el l -NFA resultant de fer la reunió d’aquests dos. Resum: A partir d’un l -NFA qualsevol i des de la vista de consulta, s’accedeix a l’assistent d’operacions que proposarà a l’usuari una selecció de l -NFA amb el mateix alfabet que l’original, per a que aquest en trii un i finalment obtenir aixi el l -NFA reunió. Tipus: Primari i essencial. 51 Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1. Selecciona un l -NFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó d’ “Operacions” 4. Mostra un assistent 5. Selecciona “Reunió” 6. Selecciona amb quin l -NFA dels proposats vol fer la reunió 7. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de fer la reunió. 8. Es crea el nou l -NFA Taula 4.27: Reunió l -NFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Concatenació l -NFA. Actors: Usuari. Propòsit: A partir de dos l -NFA, obtenir el l -NFA resultant de fer la concatenació d’aquests dos. Resum: A partir d’un l -NFA qualsevol i des de la vista de consulta, s’accedeix a l’assistent d’operacions que proposarà a l’usuari una selecció de l -NFA amb el mateix alfabet que l’original, per a que aquest en trii un i finalment obtenir aixi el l -NFA concatenació. 52 Tipus: Primari i essencial. Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1. Selecciona un l -NFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó d’ “Operacions” 4. Mostra un assistent 5. Selecciona “Concatenació” 6. Selecciona amb quin l -NFA dels proposats es vol fer la concatenació 7. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de fer la concatenació. 8. Es crea el nou l -NFA Taula 4.28: Concatenació l -NFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Kleene l -NFA. Actors: Usuari. Propòsit: A partir d’un l -NFA, obtenir el l -NFA resultant de fer el tancament de Kleene d’aquest. Resum: A partir d’un l -NFA qualsevol i des de la vista de consulta, s’accedeix a l’assistent d’operacions, es selecciona la operació “Tancament de Kleene” i es segueix l’assistent que guiarà a l’usuari durant tot el procés per obtenir aixi el l -NFA resultant. 53 Tipus: Primari i essencial. Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1. Selecciona un l -NFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó d’ “Operacions” 4. Mostra un assistent 5. Selecciona “Tancament de Kleene” 6. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de fer el tancament de Kleene. 7. Es crea el nou l -NFA Taula 4.29: Tancament de Kleene l -NFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Tancament Positiu l -NFA. Actors: Usuari. Propòsit: A partir d’un l -NFA, obtenir el l -NFA resultant de fer el tancament positiu d’aquest. Resum: A partir d’un l -NFA qualsevol i des de la vista de consulta, s’accedeix a l’assistent d’operacions, es selecciona la operació “Tancament positiu” i es segueix l’assistent que guiarà a l’usuari durant tot el procés per obtenir aixi el l -NFA resultant. 54 Tipus: Primari i essencial. Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1. Selecciona un l -NFA 2. Mostra una nova finestra amb els detalls 3. Prem el botó d’ “Operacions” 4. Mostra un assistent 5. Selecciona “Tancament Positiu” 6. Segueix els passos de l’assistent. Escriu el nom de la nova instància que es crearà com a resultat de fer el tancament positiu. 7. Apareix el nou l -NFA a la llista de representacions Taula 4.30: Tancament Positiu l -NFA Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. 4.1.3.4 Especificació de casos d’ús d’expressions regulars •Cas d’ús: Crear nova ER. Actors: Usuari. Propòsit: Crear una nova instància d’expressió regular. Resum: Mitjançant l’ús d’un assistent es crearà una nova instància d’expressió regular. Tipus: Primari i essencial. Curs típic d’esdeveniments: 55 Accions de l’actor Resposta del sistema 1. Accedir a l’aplicació 2. Selecciona Arxiu >> Nou 3. Mostra l’assistent per a la creació d’una nova instància 4. Seleccionar Expressió regular. Segons vagi avançant l’assistent anar introduint el nom, l’alfabet i la pròpia expressió regular. 5. Es crea la instància d’Expressió regular Taula 4.31: Nou_ER Errors possibles: –Ja existeix una representació amb aquest nom. –Errors en introduir les dades. Cursos alternatius: En cas d’error l’usuari rebrà un missatge diferent segons el tipus d’error. Podrà tornar a introduir les dades que eren errònies. •Cas d’ús: Suprimir ER. Actors: Usuari. Propòsit: Esborrar una instància d’expressió regular. Resum: Un cop l’usuari hagi entrat a l’aplicació, hagi seleccionat alguna instància d’expressió regular i premi el botor “Esborrar”, s’esborrarà l’expressió regular seleccionada. Tipus: Primari i essencial. Curs típic d’esdeveniments: 56 Accions de l’actor Resposta del sistema 1. Seleccina una instància 2. Prem el botó “Esborrar” 3. S’esborra la instància seleccionada Taula 4.32: Sup_ER Errors possibles: –S’intenta esborrar sense seleccionar cap instància. Cursos alternatius: En cas d’error l’usuari rebrà un missatge informat de que no ha seleccionat cap instància. •Cas d’ús: Consultar ER. Actors: Usuari. Propòsit: Consultar una instància d’expressió regular. Resum: Consultar els elements que formen una expressió regular (nom, alfabet i expressió regular). Tipus: Primari i essencial. Curs típic d’esdeveniments: Accions de l’actor Resposta del sistema 1. Selecciona una instància 2. Mostra una finestra nova amb els detalls Taula 4.33: Consultar_ER Errors possibles: - Cursos alternatius: - 57 •Operació: Reunió_DFA(nom, nom_DFA2) Responsabilitat: Crear un nou DFA que sigui el resultat d’aplicar l’operació de reunió entre el DFA identificat amb ’nom’, i el DFA identificat amb ’nom_DFA2’. Precondicions: Ha d’existir una instància amb identificador ’nom’ i ’nom_DFA2’. Postcondicions: Creació d’un nou DFA resultat de la reunió del DFA identificat amb ’nom’ amb el DFA identificat amb ’nom_DFA2’. Sortida: Nou DFA creat. •Operació: Interseccio_DFA(nom, nom_DFA2) Responsabilitat: Crear un nou DFA que sigui el resultat d’aplicar l’operació de intersecció entre el DFA identificat amb ’nom’, i el DFA identificat amb ’nom_DFA2’. Precondicions: Ha d’existir una instància amb identificador ’nom’ i ’nom_DFA2’. Postcondicions: Creació d’un nou DFA resultat de la intersecció del DFA identificat amb ’nom’ amb el DFA identificat amb ’nom_DFA2’. Sortida: Nou DFA creat. •Operació: Concatenació_DFA(nom, nom_DFA2) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’operació de concatenació entre el DFA identificat amb ’nom’, i el DFA identificat amb ’nom_DFA2’. Precondicions: Ha d’existir una instància amb identificador ’nom’ i ’nom_DFA2’. Postcondicions: Creació d’un nou l -NFA resultat de la concatenació del DFA identificat amb ’nom’ amb el DFA identificat amb ’nom_DFA2’. Sortida: Nou l -NFA creat. 64 •Operació: Kleene_DFA(nom) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’operació de tancament de Kleene sobre el DFA identificat amb ’nom’. Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: Creació d’un nou l -NFA resultat de fer el tancament de Kleene sobre el DFA identificat amb ’nom’. Sortida: Nou l -NFA creat. •Operació: Tanc_pos_DFA(nom) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’operació de tancament positiu sobre el DFA identificat amb ’nom’. Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: Creació d’un nou l -NFA resultat de fer el tancament positiu sobre el DFA identificat amb ’nom’. Sortida: Nou l -NFA creat. 4.3.2 Conctracte de les operacions de NFA •Operació: Nou_NFA(nom, cjt_estats,alfabet,transicions,cjt_inicials,cjt_finals) Responsabilitat: Crear una nova instància de NFA. Precondicions: Que no existeixi cap altra instància de representació de llenguatge formal que tingui el mateix nom. Postcondicions: Creació d’un nou NFA amb els paràmetres passats. Sortida: el NFA creat. 65 •Operació: Sup_NFA(nom) Responsabilitat: Esborrar la representació de llenguatge formal identificada pel nom. Precondicions: Ha d’existir una instància amb aquest nom. Postcondicions: Supressió de la instància amb el nom donat. Sortida: - •Operació: Consultar_NFA(nom) Responsabilitat: Consultar tota la informació associada a la instància de NFA identificada pel nom(nom, conjunt d’estats, alfabet, la funció de transició, estats inicials i els estats finals). Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: - Sortida: Els paràmetres associats al NFA. •Operació: Reconèixer_mot_NFA(nom, mot) Responsabilitat: Determinar si el NFA identificat amb ’nom’ reconeix el mot donat. Precondicions: El mot ha de ser no nul. Ha d’existir una instància amb identificador ’nom’. Postcondicions: - Sortida: Cert si la representació reconeix el mot, fals altrament 66 •Operació: Determinitzar_NFA(nom) Responsabilitat: Crear un nou DFA que sigui el resultat d’aplicar l’algorisme de determinització sobre el NFA identificat amb ’nom’. Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: Creació d’un nou DFA resultat de la determinització del NFA identificat amb ’nom’. Sortida: Nou DFA creat. •Operació: Reunió_NFA(nom, nom_NFA2) Responsabilitat: Crear un nou NFA que sigui el resultat d’aplicar l’operació de reunió entre el NFA identificat amb ’nom’, i el NFA identificat amb ’nom_NFA2’. Precondicions: Ha d’existir una instància amb identificador ’nom’ i ’nom_NFA2’. Postcondicions: Creació d’un nou NFA resultat de la reunió del NFA identificat amb ’nom’ amb el NFA identificat amb ’nom_NFA2’. Sortida: Nou NFA creat. •Operació: Interseccio_NFA(nom, nom_MFA2) Responsabilitat: Crear un nou NFA que sigui el resultat d’aplicar l’operació de intersecció entre el NFA identificat amb ’nom’, i el NFA identificat amb ’nom_DFA2’. Precondicions: Ha d’existir una instància amb identificador ’nom’ i ’nom_NFA2’. Postcondicions: Creació d’un nou NFA resultat de la intersecció del NFA identificat amb ’nom’ amb el NFA identificat amb ’nom_NFA2’. Sortida: Nou NFA creat. 67 •Operació: Concatenació_NFA(nom, nom_NFA2) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’operació de concatenació entre el NFA identificat amb ’nom’, i el NFA identificat amb ’nom_NFA2’. Precondicions: Ha d’existir una instància amb identificador ’nom’ i ’nom_NFA2’. Postcondicions: Creació d’un nou l -NFA resultat de la concatenació del NFA identificat amb ’nom’ amb el NFA identificat amb ’nom_NFA2’. Sortida: Nou l -NFA creat. •Operació: Kleene_NFA(nom) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’operació de tancament de Kleene sobre el NFA identificat amb ’nom’. Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: Creació d’un nou l -NFA resultat de fer el tancament de Kleene sobre el NFA identificat amb ’nom’. Sortida: Nou l -NFA creat. •Operació: Tanc_pos_NFA(nom) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’operació de tancament positiu sobre el NFA identificat amb ’nom’. Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: Creació d’un nou l -NFA resultat de fer el tancament positiu sobre el NFA identificat amb ’nom’. Sortida: Nou l -NFA creat. 68 4.3.3 Conctracte de les operacions de l -NFA •Operació: Nou_ l -NFA(nom, cjt_estats,alfabet,transicions,cjt_inicials,cjt_finals) Responsabilitat: Crear una nova instància de l -NFA. Precondicions: Que no existeixi cap altra instància de representació de llenguatge formal que tingui el mateix nom. Postcondicions: Creació d’un nou l -NFA amb els paràmetres passats. Sortida: el l -NFA creat. •Operació: Sup_ l -NFA(nom) Responsabilitat: Esborrar la representació de llenguatge formal identificada pel nom. Precondicions: Ha d’existir una instància amb aquest nom. Postcondicions: Supressió de la instància amb el nom donat. Sortida: - •Operació: Consultar_ l -NFA(nom) Responsabilitat: Consultar tota la informació associada a la instància de l -NFA identificada pel nom(nom, conjunt d’estats, alfabet, la funció de transició, estats inicials i els estats finals). Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: - Sortida: Els paràmetres associats al l -NFA. 69 •Operació: Reconèixer_mot_ l -NFA(nom, mot) Responsabilitat: Determinar si el l -NFA identificat amb ’nom’ reconeix el mot donat. Precondicions: El mot ha de ser no nul. Ha d’existir una instància amb identificador ’nom’. Postcondicions: - Sortida: Cert si la representació reconeix el mot, fals altrament •Operació: l -NFA_to_NFA(Int:id) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’algorisme d’eliminació de l -transicions sobre el l -NFA identificat amb ’nom’. Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: Creació d’un nou NFA resultat de la supressió de les l -transicions del l -NFA identificat amb ’nom’. Sortida: Nou NFA creat. •Operació: Reunió_ l -NFA(nom, nom_ l -NFA2) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’operació de reunió entre el l -NFA identificat amb ’nom’, i el l -NFA identificat amb ’nom_ l -NFA2’. Precondicions: Ha d’existir una instància amb identificador ’nom’ i ’nom_ l -NFA2’. Postcondicions: Creació d’un nou l -NFA resultat de la reunió del l -NFA identificat amb ’nom’ amb el l -NFA identificat amb ’nom_ l -NFA2’. Sortida: Nou l -NFA creat. 70 •Operació: Concatenació_ l -NFA(nom, nom_ l -NFA2) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’operació de concatenació entre el l -NFA identificat amb ’nom’, i el l -NFA identificat amb ’nom_ l - NFA2’. Precondicions: Ha d’existir una instància amb identificador ’nom’ i ’nom_ l -NFA2’. Postcondicions: Creació d’un nou l -NFA resultat de la concatenació del l -NFA identificat amb ’nom’ amb el l -NFA identificat amb ’nom_ l -NFA2’. Sortida: Nou l -NFA creat. •Operació: Kleene_ l -NFA(nom) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’operació de tancament de Kleene sobre el l -NFA identificat amb ’nom’. Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: Creació d’un nou l -NFA resultat de fer el tancament de Kleene sobre el l -NFA identificat amb ’nom’. Sortida: Nou l -NFA creat. •Operació: Tanc_pos_ l -NFA(nom) Responsabilitat: Crear un nou l -NFA que sigui el resultat d’aplicar l’operació de tancament positiu sobre el l -NFA identificat amb ’nom’. Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: Creació d’un nou l -NFA resultat de fer el tancament positiu sobre el l -NFA identificat amb ’nom’. Sortida: Nou l -NFA creat. 71 4.3.4 Conctracte de les operacions d’expressions regulars •Operació: Nou_ER(nom, alfabet, expressió regular) Responsabilitat: Crear una nova instància de ER. Precondicions: Que no existeixi cap altra instància de representació de llenguatge formal que tingui el mateix nom. Postcondicions: Creació d’un nova ER amb els paràmetres passats. Sortida: la ER creada. •Operació: Sup_ER(nom) Responsabilitat: Esborrar la representació de llenguatge formal identificada pel nom. Precondicions: Ha d’existir una instància amb aquest nom. Postcondicions: Supressió de la instància amb el nom donat. Sortida: - •Operació: Consultar_ER(nom) Responsabilitat: Consultar tota la informació associada a la instància de ER identificada pel nom (nom, alfabet, expressió regular). Precondicions: Ha d’existir una instància amb identificador ’nom’. Postcondicions: - Sortida: Els paràmetres associats a la ER. 72 •Operació: Reconèixer_mot_ER(nom, mot) Responsabilitat: Determinar si la ER identificada amb ’nom’ reconeix el mot donat. Precondicions: El mot ha de ser no nul. Ha d’existir una instància amb identificador ’nom’. Postcondicions: - Sortida: Cert si la representació reconeix el mot, fals altrament •Operació: ER_to_ l -NFA(nom) Responsabilitat: Crear un nou l -NFA que sigui el resultat de transformar l’expressió regular identificada amb ’nom’ en l -NFA. Precondicions: Ha d’existir una instància de ER amb identificador ’nom’. Postcondicions: Creació d’un nou l -NFAresultat de la transformació de la ER identificada amb ’nom’. Sortida: Nou l -NFA creat. 73 •Titulo de Formulario: en aquesta part apareixerà el nom de l’aplicació. •Nombre de menu: Correspon a la barra de menús amb les diferents opcions existents. Al fer clic amb el ratolí sobre alguna d’aquestes opcions, es desplegaran submenús oferint les diferents opcions disponibles. •Els dos botons de la dreta estan pensats per tenir a mà dos funcions que també hi són en els menús però que per la naturalesa de la funció a la que criden, son funcions que es faran servir sovint, així conve tenir-les a la vista. Aquestes dos funcions seran les de crear i esborrar una representació de llenguatge formal. •El recuadre gran del mig correspon a la llista d’instàncies creades on cada fila correspon a una instància de representació de llenguatge formal. S’opta per fer servir una llista ja que com marquen els requisits de l’aplicació, en un moment donat es pot tenir més d’una representació, així que s’havia de poder accedir a una representació en concret i poder veure quines són les representacions que s’han creat fins al moment. Quan és creï una nova representació aquesta s’afegira a la llista, i quan s’esborri, s’esborrarà també de la llista. 5.2.2.3 Vista de consulta A continuació es mostra un esquema dels components que contindrà la vista de consulta així com la seva ubicació dins d’aquesta vista (Veure figura 5.3). 80 Figura 5.3: Esquema vista de consulta Tot seguit es detallen les diferents parts d’aquest esquema així com una descripció del seu comportament. •Tipus: A la part superior de la vista apareix el tipus de representació que estem consultant (DFA, NFA, l -NFA, expressió regular). •Atributs: Aquí es mostraran tots els atributs associats al tipus de representació que estem consultant. 81 •Reconèixer mot: En aquesta secció de la vista s’utilitza per determinar si la representació que estem consultant reconeix el mot que escrivim en el camp de text d’aquesta secció. •Botó sortir: Prement aquest botó es tanca la vista de consultes per retornar a la vista general. •Botó operacions: Prement aquest botó és canvia de vista cap a la vista d’assistent d’operacions. •Botó Transformacions: Prement aquest botó és canvia de vista cap a la vista d’assistent de transformacions. 5.2.2.4 Vista d’assistents A continuació es mostra un esquema dels components que contindrà la vista de consulta així com la seva ubicació dins d’aquesta vista (Veure fiura 5.4). Figura 5.4: Esquema vista d’assistents Tot seguit es detallen les diferents parts d’aquest esquema així com una descripció del seu comportament. 82 •Descripció: A la part superior de la vista apareix una breu descripció de quina informació està mostrant actualment l’assistent i quines dades espera de l’usuari. •Formulari: L’objectiu d’aquesta secció és que l’usuari rebi la informació que li transmet l’assistent i, si s’escau, que inserti la informació sol·licitada. Per a fer això és mostraran diferents elements de formulari com llistes, camps de text, menús desplegables, etc. •Botó cancelar: Prement aquest botó es cancela l’assistent i es tanca la vista retornant a la vista anterior. •Botó següent: Prement aquest botó s’avança pel flux d’assistents. •Botó anterior: Prement aquest botó es retroecedeix pel flux d’assistents. 5.3 Capa del Domini 5.3.1 Funcions de la capa del Domini La capa domini és la que manté tota la lògica i les regles de negoci. S’encarrega de validar les dades introduïdes en la capa de presentació, realitzar operacions i càlculs amb les dades. També gestiona les interaccions amb la capa de presentació. Aquesta capa es relaciona amb la capa de presentació passant-li les respostes i resultats, i rebent-ne els esdeveniments externs (crides a accions) i consultes. També es relaciona amb la capa de gestió de dades passant-li les operacions de consulta i modificacions de dades, i rebent-ne les respostes i resultats. S’enccaregarà de: •Assabentar-se dels esdeveniments. •Controlar-ne la valides. •Executar les accions encomanades. •Assabentar-se de les consultes. •Obtenir-ne els resultat. •Comunicar la resposta. 83 5.3.2 Disseny de la capa del Domini Per a fer el disseny de la capa de domini ens basarem en l’especificació obtinguda prèviament en el capítol d’Especificació. Un dels aspectes més importants en el procés d’especificació és el del disseny conceptual, ja que en aquest moment, pren molta rellevància. Tot el disseny de la capa del domini està basat en aquest disseny conceptual. Així doncs tenint en compte que el model de programació és el de programació orientada a objectes, el disseny conceptual citat anteriorment i les funcions a desenvolupar per aquesta capa de l’arquitectura del programari tenim que el disseny ha de incloure un objecte que representi DFA, un altra objecte que representi NFA, un altra objecte que representi l -NFA i un altra que representi les expressions regulars. Els objectes de DFA, NFA i l -NFA, que són diferents tipus d’autòmat, hauran de tenir com a atributs els atributs que defineixen a la realitat els autòmats, és a dir, un conjunt d’estats, un alfabet (un conjanut de símbols), una funció de transició, un subconjunt dels estats que siguin els estats inicials, i un subconjunt dels estats que siguin els estats finals. L’únic canvi és que la funció de transició es representara com una matriu on cada fila correspondrà a cada un dels estats del autòmat, cada columna cada símbol de l’alfabet, i la intersecció fila-columna representa l’estat destí per aquell estat i símbol. L’objecte que representa expressions regulars tindrà com a atributs la pròpia expressió regular i un alfabet. Finalment i per ajustar-nos a la funció que ha de fer aquesta capa, es crearà un objecte que agruparà tots els altres objectes, oferint així una interfície única a la capa de representació. En funció de l’operació sol·licitada per l’usuari a la capa de representació, aquest objecte delegarà l’operació a l’objecte pertinent (DFA, NFA, l -NFA, i expressió regular). 5.4 Capa de gestió de dades 5.4.1 Funcions de la capa de gestió de dades La capa de gestió de dades sap on i com estan emmagatzemades les dades, però ignora com tractar-les. 84 Aquesta capa es relaciona amb la capa de domini passant-li les respostes i resultats, i rebentne les operacions de consulta i modificació de dades. S’encarregarà de: •Permetre-li al domini ignorar on són les dades. •Permetre que determinats objectes del domini siguin persistents. 5.4.2 Disseny de la capa de gestió de dades Aquesta capa no serà dissenyada ni implementada doncs d’acord amb les especificacions no requereix d’emmgatzemar dades de forma persistent. Tot i així, tal i com es comenta en l’apartat de millores, una funcionalitat destacable a afegir seria l’opció de permetre desar i recuperar una isntància de representació de llenguatge formal en un fitxer. En aquest cas 85 s’hauria de dissenyar en aquest punt per poder-la implementar posteriorment. 86 Capítol 6 Implementació Finalment, després d’haver realitzat el disseny ve l’etapa d’implementació, que correspon a la codificació del programa. En aquest apartat comentarem les tecnologies que s’han fet servir per portar a terme la implementació i s’explicarà algun dels seus mètodes més rellevants. 6.1 Tecnologies a fer servir En aquest punt es mostraran les diferents tecnologies que es faran servir per a la implementació. L’elecció de les tecnologies sempre s’ha fet en base a tota la feina feta anteriorment, és a dir, s’ha tingut en compte l’anàlisi de requisits, l’especificació i el disseny. •Java: Hi ha diferents motius que porten a l’elecció de Java com a llenguatge de programació principal en el procés de la implementació. Un d’ells és que Java és un llenguatge orientat a objectes, seguint així la metodologia de programació que s’ensenya a la facultat i probablement una de les més esteses avui dia. Un altre dels motius és que Java és multiplataforma, permetent així que el programa pugui ser executat en diferents plataformes sense modificar ni una sola línia de codi, complint així un dels requisits no funcionals. I finalment Java és gratuït i de codi obert. De les versions disponibles dels kits de desenvolupament de Java s’opta per l’última versió disponible en el moment d’iniciar aquesta etapa que correspon a la versió JDK 1.6.0_19. 87 •Swing: Swing és una biblioteca per a Java. En ella es poden trobar widgets per a la creació d’interfícies gràfiques d’usuari tals com caixes de text, botons o desplegables entre molts altres. Swing forma part de les Java Foundation Classes, que és un Framework per a la creació d’interfícies gràfiques d’usuari portables basades amb Java. A més Swing permet mantenir la independència entre diferents plataformes. Swing és gratuït i de codi obert. •Llenguatge Dot: És un llenguatge de text plà per descriure grafs. •Graphviz Dot: És una eina gratuita i de codi obert que interpreta descripcions de grafs fetes amb llenguatge Dot produint com a sortida una imatge en diferents formats amb el dibuix del graf. 6.2 Entorn de desenvolupament Per realitzar la implementació del projecte és necessari tenir configurat un entorn de desenvolupament. Com a entorn integrat de desenvolupament o IDE (de l’anglès Integrated development environment) s’ha escollit NetBeans versió 6.8. L’elecció es deu principalment a la gran integració de la que disposa NetBeans amb les biblioteques de Swing, oferint un entorn molt senzill i amagable pel desenvolupament d’aplicacions que facin ús d’aquesta biblioteca. La principal competència de l’IDE NetBeans és l’IDE Eclipse, el qual no disposa d’una integració de swing ni facilita el desenvolupament d’aplicacions usant Swing. També s’escull NetBeans perquè és multiplataforma i això ha permés que tot i que principalment s’hagi desenvolupat sobre un entorn linux, puntualment s’hagi pogut desenvolupar sobre un entorn Windows sense perdre compatibilitat o alguna de les funcions de l’IDE. 6.3 Diagrama de classes A continuació es mostra un diagrama amb les principals classes que s’implementen. 88 Figura 6.1: Diagrama de classes •GUI: classe que conté tota la interfície gràfica d’usuari. •Framework: classe que per un cantó interactua amb la interfície gràfica rebent les seves peticions i transmetent-li els resultats, i per l’altre interactua amb la classe ReprLleng- Form passant-li les peticions d’operacions a realitzar. •ReprLlengForm: classe que defineix alguns mètodes i atributs que són comuns a tots els tipus de representacions de llenguatges formals, perquè després, cada una d’aquestes representacions les hereti. •Autòmat: classe que hereta de ReprLlengForm i defineix nous mètodes i atributs comuns per les representacions de tipus autòmat. •DFA/NFA/LNFA: classes que hereten d’Automat i acaben de definir nous mètodes necessaris per cada cas concret de representació. 89 7.1.2 Prova de supressió de l -transicions d’un l -NFA En aquesta prova es mostrarà el procés per obtenir un NFA equivalent a partir d’un l -NFA. (extret de [5], Exemple 4.14). Com abans, primer veurem el problema i la solució que es mostra en llibre. l -NFA d’origen, anomenem-lo N: Figura 7.6: l -NFA N L’autòmat Nté la següent taula de transicions: Figura 7.7: Taula de trnasicions de N Ara introduïm el l -NFA Na l’aplicació: 96 Figura 7.8: l -NFA N I finalment el NFA obtingut mitjançant l’aplicació a partir del l -NFA N: 97 Figura 7.9: NFA obtingut a partir de N Com abans si substituïm: •0 per A •1 per B •2 per C •3 per E •4 per D Obtenim l’autòmat esperat i que coincideix amb el resultat obtingut del llibre. 7.1.3 Prova de determinització d’un NFA Suposem un NFA que reconegui un llenguatge format pels mots que o començen per b o tenen un nombre parell de ’a’ en l’inici del mot, continuen amb un nombre imparell de ’b’ superior a tres i acaben amb el símbol ’a’. 98 Formalment, el llenguatg reconegut L= (aa)∗b(bb)+a. Visualment un dels NFA que reconegués aquest llenguatge té la forma: Figura 7.10: NFA que reconeix L Així doncs introduïm aquest NFA a l’aplicació: Figura 7.11: NFA introduït a l’aplicació I tot seguint fem la transformació a DFA obtenint: 99 Figura 7.12: DFA obtingut On observant l’autòmat resultant es veu clarament que reconeix exactament el mateix llenguatge L. 7.1.4 Prova d’obtenció d’un autòmat a partir d’una expressió regular Partint d’una expressió regular es vol provar tot el procés fins a arribar a un DFA. El procés sencer és: d’expressió regular es transforma a l -NFA, de l -NFA s’eliminen les l -transicions per obtenir un NFA, i del NFA es determinitza per obtenir el DFA resultant. Es parteix de l’expressió regular: er1=(a∗b∗)+. Primer de tot es crea aquesta mateixa expressió regular en l’aplicació: 100 Figura 7.13: er1 en l’aplicació Tot seguit es fa la transformació a l -NFA: Figura 7.14: l -NFA obtingut a partir d’er1 101 Un cop tenim el l -NFA el següent pas és eliminar les l -transicions. Figura 7.15: NFA obtingut després d’eliminar les l -transicions I per últim només resta determinitzar el NFA per obtenir el DFA. 102 Figura 7.16: DFA equivalent a er1 103 104 Capítol 8 Revisió de la planificació 8.1 Desenvolupament temporal La planificació inicial del projecte es va realitzar entre finals del 2009 i principis del 2010. En un principi no es va realitzar una planificació exhaustiva ni gaire precisa degut al desconeixement de la càrrega que comportaria el projecte fruit de la desconeixença del desenvolupament en general. Durant la realització del projecte han sorgit imprevistos que han fet que determinades tasques s’allarguessin més del compte i que d’altres no es poguessin finalitzar i es van haver d’acotar. En una planificació inicial es va decidir presentar el projecte a mitjans de juny del 2010, però degut al grau de complexitat de part de la implementació la planificació real es va desviar molt de la prevista i finalment es va prendre la decisió d’allargar el temps del projecte ampliant el termini d’entrega al pròxim quadrimestre. Un cop acceptat que era impossible presentar el projecte en les dates previstes inicialment, s’aprofita per fer un replantejament de l’aplicació i afegir-li un element que li dóna un valor afegit molt important: la interfície gràfica d’usuari. En la idea inicial s’havia pres la decisió de no desenvolupar cap interfície gràfica per l’aplicació i que aquesta funcionés directament sobre línia de comandes, però un cop endarrerida la data, tant tutor com alumne van estar d’acord que era molt interessant l’opció de disposar d’una interfície gràfica senzilla, útil i amigable. Hi ha tasques a les quals s’ha dedicat bastant de temps en comparació d’altres, especialment en les primeres etapes del projecte. El projecte va sorgir d’una idea que va anar madurant i prenent forma al llarg de moltes reunions. 105 ha estat la desviació de la planificació temporal que han portat altres objectius més prioritaris i la complexitat del problema, complexitat que es va infravalorar inicialment. 9.3 Possibles ampliacions i millores A mesura que s’anava avançant en les diferents etapes del projecte, varies ampliacions i millores anaven sorgint. Algunes d’elles són: •Adaptar l’aplicació a la web. Cada cop més totes les aplicacions es van mudant dels nostres ordinadors cap a la web. Així se simplifica l’accés a l’usuari i s’optimitzen les tasques de manteniment de l’aplicació. •Dissenyar i desenvolupar un motor de simplificació d’expressions regulars. •Conjuntament amb l’anterior, dissenyar i desenvolupar la conversió de DFA a expressió regular. •Estudiar amb detall la interactibililtat dels grafs i quines solucions es poden implantar per tenir un sistema que permiti a l’usuari interactuar amb els grafs en lloc de mostrarlos com una imatge estàtica. •Implementar la possibilitat de poder desar en un fitxer una o més d’una instància de llenguatge formal. Implementar la possibilitat de recuperar d’un fitxer una o més d’una instància de llenguatge formal. •Estudiar si es poden afegir noves operacions. •Estudiar noves formes de representació de llenguatges formals i si s’escau implementarles. •En el cas d’alguna de les operacions que existeixi més d’un algorisme per resoldre la operació, oferir amb quin dels algorismes es vol fer el càlcul. A grans trets aquestes són les principals millores pensades. Cal destacar que durant el desenvolupament del projecte constantment apareixien possibles millores tant a nivell d’usabilitat de l’aplicació com d’addició de noves funcionalitats. 112 9.4 Conclusions personals A nivell personal els objectius han estat àmpliament satisfets. L’objectiu principal era el de seguir aprenent i ampliar els coneixements adquirits a l’assignatura d’ALCC, i finalment s’ha complert. A l’iniciar el projecte només coneixia el que havia après durant l’assignatura d’ALCC, on només es tracten els DFA i sense massa profunditat. Al acabar el projecte es coneix amb més profunditat els DFA i s’aprén des de zero i amb un grau de profunditat equivalent a l’obtingut del DFA, els NFA, els l -NFA, les seves operacions i transformacions, i les expressions regulars. Ara que ja s’ha acabat estic molt content per haver seguit aprenent aspectes en aquest àmbit, però segueixo amb ganes d’aprendre. Per altra banda la realització d’una aplicació que pot ajudar a qualsevol persona i en especial a algun estudiant a aprendre és molt enriquidor personalment. Si em poso en la pell d’un estudiant que disposés d’una aplicació com aquesta per ajudar a estudiar, probablement estaria eternament agraït a aquella persona que l’hagués fet per facilitar-me la vida. De fet aquesta sensació l’he tingut diverses vegades al llarg de tota la titulació. Així doncs pensar que potser algun dia si algú fa servir aquesta aplicació pugui pensar això mateix sobre aquest programa ja m’omple de satisfacció. Així doncs, globalment quedo plenament satisfet amb el resultat del projecte, i amb la sensació que amb més temps hagués pogut fer una aplicació amb moltes més funcionalitats i molt més útil per molta més gent. Però suposo que la sensació és inevitable doncs a tota aplicació se li pot afegir alguna cosa perquè sigui una mica millor, o ofereixi noves funcionalitats. No descarto que en un futur a títol personal i per plaer, segueixi aprenent sobre la teoria de la computació i segueixi ampliant el programa. 113 Bibliografia [1] http://www.cs.usfca.edu/~jbovet/vas.html [2] http://www46.homepage.villanova.edu/timothy.m.white/ [3] http://www.cs.duke.edu/csed/jflap/ [4] http://osteele.com/tools/reanimator/ [5] Llenguatges, gramàtiques i autòmats. Curs bàsic. Rafel Cases i Lluís Màrquez. Edicions UPC. Segona edició (Aula Politècnica) 2003, Barcelona. [6] Apunts de l’assignatura d’ALCC, Antoni Lozano [7] http://www.wikipedia.org 114