Simulador de Automato Finito Nao-Deterministico AFND - Implementacao e Testes

Um Autômato Finito nãoDeterminístico AFND é uma máquina de estados finita onde para cada par de estado e símbolo de entrada pode haver vários próximos estados possíveis ou nenhum estado possível Isso o distingue do autômato finito determinístico AFD onde o próximo estado possível é univocamente determinado com isso o AFND tem o poder de estar em vários estados ao mesmo tempo Essa habilidade é expressa com frequência como capacidade de adivinhar algo sobre entrada Como em um AFD o AFND tem um conjunto finito de estados um conjunto finito de símbolos de entrada um estado inicial e um conjunto de estados finais e a função de transição Na função de transição está a diferença entre um AFD e AFND Para um AFND é uma função que recebe um estado e um símbolo de entrada como argumentos igual o AFD mas retorna um conjunto de zero um ou mais estados em vez de retornar um estado como no AFD Considere a Figura 1 que apresenta o diagrama de estados de AFND M que reconhece todas as palavras sobre o alfabeto a b que terminam com ab Figura 1 Diagrama de Estados para um automâto finito nãodeterminístico A seguir é apresentado a descrição formal quíntupla do AFND M Q q0 q1 q2 a b q0 q0 F q2 a B q0 q0q1 q0 q1 Ø q2 q2 Ø Ø A linguagem aceita pelo AFND M é dado por LM W q0 W F Ø Isto é LM é o conjunto de todas as palavras W tal que o resultado da intersecção de q0 W com F é diferente de vazio pois estamos comparando conjuntos Simulador de Autômatos Finito NãoDeterminístico Objetivo O objetivo deste trabalho é escrever um programa que tenha como entrada um AFND especificado em um arquivo texto o programa deve simular qualquer AFND informado pelo arquivo e testar várias palavras sobre alfabeto do AFND O arquivo texto deverá ter a seguinte configuração 1 Na primeira linha os símbolos do alfabeto de entrada com letras sempre em minúsculo em ordem alfabética sempre começando por a e sem espaços em branco entre os símbolos o tamanho do alfabeto é limitado a 10 símbolos na primeira linha Por exemplo se quiser um alfabeto com 5 símbolos como teríamos abcde tudo junto 2 Na segunda linha o número de Q estados para facilitar a implementação o estado inicial será sempre o primeiro estado q0 e qualquer AFND terá no máximo 20 estados q0 q1 q19 ou seja Q20 3 Na terceira linha temos um número F indicando a quantidade de estados finais e na linha seguinte quarta linha a lista dos estados finais separados por espaço em branco na mesma linha considere que F Q 4 Na quinta linha temos o número de N transições do AFND e nas N linhas seguintes as transições especificadas no seguinte formato separadas por espaço em branco estado corrente branco símbolo em branco estado chegada 5 Ao final das N transições teremos uma linha com um inteiro T especificando o número de palavras que deverão ser testadas no AFND as palavras estarão cada uma em uma linha contendo somente os símbolos do alfabeto de entrada Considere também que cada palavra terá no máximo 100 caracteres Saída O programa deverá conforme especificado no arquivo de entrada processar a as palavras usando AFND especificado e depois escrever o resultado na tela com as seguintes sentenças palavra processada e a informação OK caso do AFND tenha parado o processamento no estado de aceitação e not OK caso contrário Considere que termos as seguintes restrições para cada conjunto Exemplo de entrada ab 3 1 2 4 0 a 0 0 a 1 0 b 0 1 b 2 5 aab aababab ababb bbaa b Exemplo de saída 1 aab OK 2 aababab OK 3 ababb not OK 4 bbaa not OK 5 b not OK Observações importantes O trabalho será avaliado de acordo com os seguintes critérios Funcionamento do programa caso programa apresentarem warning ao serem compilados serão penalizados Após a execução o programa deve finalizar com retorno igual a 0 O trabalho deve ser desenvolvido na linguagem C e será testado usando o compilador do CodeBlocks 1712 O quão fiel é o programa quanto à descrição do enunciado principalmente ao formato de do arquivo de entrada Clareza e organização programas com código confuso linhas longas variáveis com nomes nãosignificativos e desorganizado sem indentação sem comentários também serão penalizados