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

O projeto consiste em gerar um autômato finito deterministico 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 as reconhecerá caso essa expressão pertença a 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 caractere vazio, o "@" representa a Linguagem Vazia;
•  
• As entradas serão compostas por no máximo 100 caracteres("0 ou "1"); 
•  
• 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. ).;
•  
•  
• Quando o caractere 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 String vazia "" passada como argumento; 
•  
• A Linguagem Vazia("@", relacionado ao objeto LinguagemVazia() em util.expressoesRegulares) aparecerá somente na definição da linguagem e não na entrada , observe que o "e" aparece tanto na definição da linguagem como nas entradas(VIDE EXEMPLOS NO FINAL DA PAGINA).Atente-se para as propriedades algébricas que envolvem a linguagem vazia: 
• I)  @* = e;
• II) @ + x = x;
• III) @.x = @; 
• IV) @ = @, cuja linguagem não aceita nada, nem o "e".
•  
• A saída do autômato será true ou false , caso a entrada pertença ou não a linguagem(Vide exemplos no final);
•  
• Os exemplos no final da pagina são meramente ilustrativos e servem para teste, para construí-los você terá que usar os métodos fornecidos pelo pacote fornecido pelos monitores, as saídas do exemplo serão as saídas que seu método booleano automato.alimenta() terá que fornecer caso ele esteja corretamente implementado;  
•  
•  
• 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 esta 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.Esta 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 30/Novembro/2004 para entregar o projeto via e-mail através de um arquivo compactado   para        famv@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;
•  
• NÃO ACEITAREMOS SOB HIPÓTESE ALGUMA A ENTREGA DE OUTROS ARQUIVOS QUE NÃO SEJAM ESSES;
•  
• 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

######################################################################################################################################
Linguagem 4
(@ + 0)

ENTRADAS
e
0
1
101
010
010101010101010101010101010101
101010
1010100
1101010
1010101

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