Projeto de Teoria da Computação - 4º Período

O projeto consiste em gerar um autômato finito determinístico a partir de uma expressão regular dada como entrada (ex: (0 + e)* ). Após a construção desse autômato, serão dadas expressões regulares para serem usadas como entrada e o autômato deverá aceitá-la se e somente se essa expressão pertence à linguagem gerada pelo autômato.

LEIA COM ATENÇÃO OS DETALHES ABAIXO:   

• O alfabeto será composto apenas por  0 ou 1;
• O "e" representa o caracter vazio;
• As entradas serão compostas por no máximo 100 caracteres ("0 ou "1"); 
• Quando o caracter vazio aparecer na entrada (o "e" NA ENTRADA, NÃO NA DEFINIÇÃO DA LINGUAGEM, vide Exemplos no final desta pagina) ele virá sozinho (não ocorre coisas do tipo "0e1" pois o mesmo é equivalente a "01"). A entrada do "e" para o autômato é definida com o uso do método automato.alimenta(""), com a cadeia vazia "" passada como argumento;
• A saída do autômato será true ou false , caso a entrada pertença ou não a linguagem (vide exemplos no final);
• A linguagem usada na implementação do Projeto será JAVA (classes auxiliares da API de Java, caso necessário, até a versão do JDK 1.4.0. Dá muito bem para fazer);
• Os únicos pacotes de Java permitidos para uso (além do oferecido na pagina de Marcos Aurélio) serão java.lang.* e java.util.*, qualquer outro está PROIBIDO, caso encontremos qualquer outro, ZERO. Dá de sobra para implementar os algoritmos necessários;
• Cada aluno deverá implementar a classe Gerador, essa classe
  deverá implementar o método getAutomato(), que gera um autômato finito(em SeuAutomato) a
  partir de uma especificação dada (Linguagem), que é passada através de um objeto do tipo
  util.expressoesRegulares.ExpressaoRegular (vide pacote
  util.expressoesRegulares). Os arquivos Gerador.java e Teste.java que se encontram em http://www.cin.ufpe.br/~maas/teoria/projeto.zip  junto com o resto das classes auxiliares, servirão de  
  exemplos de como funciona a classe Gerador e de como você pode testar seu programa (Teste.java) enquanto estiver implementando-o. Está tudo bem intuitivo, evite fazer perguntas aos monitores só porque não se deu o trabalho de olhar o código e os exemplos;
• O aluno terá a até a meia noite do dia XXXXXX para entregar o projeto via e-mail através de um arquivo compactado   para         famv@cin.ufpe.br  ou   maas@cin.ufpe.br   com    o   Subject: "Projeto de Teoria - Automato";
• O aluno deverá entregar um arquivo compactado via e-mail no FORMATO ZIP com o nome <login>ProjTeoria.zip(Exemplo: famvProjTeoria.zip).NÃO NOS RESPONSABILIZAMOS por arquivos com outros nomes ou outros formatos.Este arquivo compactado deverá conter APENAS Gerador.java (com o nome do aluno nele) e um pequeno relatório (PEQUENO MESMO, no máximo 3 paginas) no formato PS,PDF ou DOC, das principais idéias usadas na implementação dos algoritmos de construção do automato e de reconhecimento das entradas;
• Cópias NÃO SERÃO TOLERADAS, caso se descubra, ZERO para os envolvidos!!!!!
• Quaisquer dúvidas falar com os monitores FranciscoValadares (famv@cin.ufpe.br) ou Marcos Aurélio (maas@cin.ufpe.br).
• Boa sorte a todos!!!

Exemplos que ajudaram nos testes no decorrer da implementação segue abaixo.

######################################################################################################################################
Linguagem 1
1

ENTRADAS
e
0
1111111111111111111111111111111111111111
0101011101010100101010100001101010
00000000000000001111111111111111111111
1
11111111111111110000000000000000000000
111000111000111000
100110
11

RESPECTIVAS SAÍDAS
false
false
false
false
false
true
false
false
false
false
######################################################################################################################################
Linguagem 2
(0 + e)*
 

ENTRADAS
e
0
1111111111111111111111111111111111111111
0101011101010100101010100001101010
00000000000000001111111111111111111111
1
11111111111111110000000000000000000000
111000111000111000
100110
00000000000000000000000000000000000000000000
 

RESPECTIVAS SAÍDAS
true
true
false
false
false
false
false
false
false
true
######################################################################################################################################
Linguagem 3
(((e+1).(0.1)*).(e+0))

ENTRADAS
10
0
1
101
010
010101010101010101010101010101
101010
1010100
1101010
1010101

RESPECTIVAS SAÍDAS
true
true
true
true
true
true
true
false
false
true