TC - Trabalho 1
Contents
1. E WSN UNIVERSIDADE DE COIMBRA Trabalho realizado por Pedro Oliveira 501062444 Rui Costa 501062452 Turma TP1 1 Introdu o O objectivo deste trabalho era implementar um simulador de Aut matos Finitos Determin sticos Dentro deste objectivo havia v rias etapas que eram pedidas e foram implementadas sendo elas Ser poss vel ao utilizador introduzir um aut mato Ler e gravar um aut mato de e para um ficheiro Rejeitar aut matos inv lidos p e aut mato que n o sejam deterministas Determinar se um aut mato aceita uma cadeia de caracteres Simular passo a passo o aut mato para diversas cadeias de caracteres O trabalho foi come ado por ser implementado em duas linguagens de programa o distintas Java e Python Tendo sido escolhida a implementa o em Python por se ter revelado mais aliciante para n s que desconhec amos a linguagem e porque se veio a revelar uma linguagem extremamente eficaz para este trabalho em espec fico 2 Manual do utilizador Neste manual de utilizador ser explicada a forma como o utilizador deve proceder de forma a interagir correctamente com o programa O menu cont m diversas op es que s o explicadas de seguida 1 Introduzir Aut mato Op o que permite introduzir um aut mato as op es Simular Aut mato e Guardar Aut mato em ficheiro t m como pr requisito a correcta execu o desta op o ou a op o Ler Aut mato de Fichei2. a o Depois de efectuados esses testes n o detecta mos nenhuma anomalia por isso a avalia o feita por n s aplica o foi muito satisfat ria Como exemplo seguem alguns dos testes efectuados Testei i q0 a gt q1 qt a gt q1 Input Resultado Esperado Resultado Obtido q0 gt Aceite q0 gt Aceite aaaaaa qi gt Aceite q1 gt Aceite Teoria da Computa o Trabalho Pr tico n 1 Teste2 i q0 0 gt q0 1 gt q1 q1 0 gt q1 1 gt q2 q2 0 gt q1 1 gt q1 qo qi aaRS l Input Resultado Esperado Resultado Obtido j q0 gt Rejeitada q0 gt Rejeitada 0 q0 gt Rejeitada q0 gt Rejeitada 00000110 qi gt Aceite q1 gt Aceite 1111111100001010 q1 gt Aceite q1 gt Aceite 111111111111111111 q2 gt Rejeitada q2 gt Rejeitada Teoria da Computa o Trabalho Pr tico n 1 Teste3 q0 q1 02 q3 q4 95 98 l a b q0 a gt q1 b gt q0 i q1 a gt q1 b gt q5 i q2 a gt q4 b gt q3 q3 a gt q1 b gt 98 i q4 a gt q4 b gt q3 q5 a gt q2 b gt q q6 a gt q6 b gt q6 l l l l qo qi Resultado Esperado Resultado Obtido q0 gt Rejeitada q0 gt Rejeitada ababa qi gt Aceite q1 gt Aceite bbaaababbbbbaaaa q6 gt Rejeitada q6 gt Rejeitada ababaaaa
3. baaaaabbbbaaaaa q1 gt Aceite q1 gt Aceite baabbaabababaaababababababababaaaaab q6 gt Rejeitada q6 gt Rejeitada Teoria da Computa o Trabalho Pr tico n 1 Teste 4 q0 a gt q0 b gt q0 q1 a gt q0 b gt q1 q0 Resultado Resultado Obtido Esperado 4 q0 gt Rejeitada q0 gt Rejeitada ababa q0 gt Rejeitada q0 gt Rejeitada Resultado Esperado Resultado Obtido q0 gt Aceite q0 gt Aceite Teoria da Computa o Trabalho Pr tico n 1
4. de proceder avalia o transita automaticamente para o final sabendo o utilizador se a cadeia ou n o aceite O que Input notas Cadeia aa Tipo de simula o 1 ou 2 Autom tica ou passo a passo Teoria da Computa o Trabalho Pr tico n 1 3 Manual do programador Na elabora o deste projecto escolhemos usar a linguagem Python Foi um desafio em duas vertentes o desenvolvimento do projecto em si e a aprendizagem de uma nova linguagem No final do desenvolvimento da aplica o cheg mos conclus o que a escolha do Python mostrou se muito lucrativa visto que esta linguagem possui caracter sticas que mostraram ser muito vantajosas para este tipo de projectos A pot ncia das suas listas e dicion rios aliados possibilidade de cria o de tuplos de vari veis permitiram nos reduzir em muito a complexidade da aplica o em compara o com outras linguagens como C e Java Como a interface n o era valorizada a interac o com o utilizador efectuada num sistema simples de consola 3 1 Gram tica Utilizada A gram tica utilizada foi baseada na referida no enunciado com pequenas modifica es que para n s melhoram a interac o com o utilizador Exemplo de Automato q0 q1 a b c q0 a gt g1 b gt g1 q1 a gt q0 b gt q0 l l l l A inser o de estados alfabeto estado inicial e estados finais igual referida no enunciado Apenas as transi
5. es s o diferentes Decidimos que era mais f cil para o utilizador inserir as transi es de cada estado numa linha s para uma melhor ordena o e distribui o do input O input de transi es acaba com uma linha em branco Todos os caracteres especiais que estejam fora do nosso abeced rio a Z ou da nossa numera o 0 9 s o ignorados do input logo n o por exemplo obrigat rio separar a inser o de estados por uma v rgula Pode se pura e simplesmente inserir um espa o ou outro car cter qualquer que esteja fora dos alfabetos referidos 3 2 Estruturas de dados Para representar o aut mato recorremos a estruturas de dados caracter sticas do Python O aut mato em si um objecto AFD que contem essas estruturas de dados Classe AFD estados alfabeto transicoes estado inicial estados finais loaded O Traduzindo para a defini o de aut mato finito Q 2 0 S F Q estados 2 alfabeto transicoes S estado inicial F estados finais Os estados alfabeto e estados finais s o representados numa lista O estado inicial uma simples string As transi es s o representadas por um dicion rio cuja chave um tuplo estado letra e conte do o estado de destino A vari vel loaded serve apenas para confirmar se o aut mato correcto e ou determin stico 3 3 Testes Foram elaborados v rios testes para avaliar a efic cia e qualidade da aplic
6. ro Estados Q q0 gl Os estados devem estar separados por caracteres que n o de A Z e 0 9 Alfabeto J a b N o relevante a forma como inserido desde que n o estejam separados por caracteres de A Z e 0 9 q0 a Devem obedecer representa o descrita no exemplo TranatedestE ol uma transi o por linha A inser o de transi es mi sao termina quando introduzida uma linha em branco E gt q1 ap s esta que avaliado o determinismo do aut mato Estado q0 E constitu do por apenas um estado inicial go Estados ql q0 Os estados devem estar separados por caracteres finais F que n o de A Z e 0 9 2 Ler Aut mato de ficheiro Op o que permite carregar um aut mato previamente guardado num ficheiro O conte do do ficheiro deve ser igual ao que t1 txt mostrado no t pico introduzir aut mato e o ficheiro deve terminar com um n Nome do ficheiro 3 Guardar Aut mato em ficheiro Permite guardar um aut mato finito determin stico gerado em um ficheiro Nome do ficheiro Teoria da Computa o Trabalho Pr tico n 1 4 Simular Aut mato Permite simular uma cadeia de s mbolos de forma a verificar se a mesma ou n o aceite pelo aut mato inserido Esta simula o pode ser feita passo a passo i e um caracter de cada vez sendo apenas necess rio pressionar o enter para que se avance para o pr ximo passo A outra forma
Download Pdf Manuals
Related Search