Implementacao_de_Automatos_Finitos

Prévia do material em texto

Implementação de Autômatos Finitos 
Paulo Renato Kinjo
1 
Curso de Ciência da Computação - Pontifícia Universidade Católica do Rio Grande do Sul 
(PUCRS) Av. Ipiranga, 6681 - Partenon - Porto Alegre/RS - CEP: 90619-900 
(paulo.kinjo)@acad.pucrs.br 
Resumo. Este artigo descreve um conjunto de classes, desenvolvidas em Java para 
a construção de Autômatos Finitos (AF). As classes apresentadas neste texto 
representam autômatos finitos determinísticos e exemplos de utilização destas 
classes serão apresentados de forma sucinta ao longo da breve descrição e ou 
implementação dos mesmos. Este trabalho faz parte da disciplina 4642C-04 
Linguagens Formais[4]. 
Palavras-chaves: Java; Conjunto de Classes; Autômatos Finitos Determinísticos; 
Linguagens Formais. 
Implementation of Finite Automata 
Abstract. This article describes a set of classes, developed in Java for building 
Finite Automata (FA). The classes presented in this text represent deterministic 
finite automata and examples of use of these classes will be presented succinctly 
throughout of this brief description or implementation thereof. This work is part of 
the discipline 4642C-04 Formal Languages[4]. 
Keywords: Java; Set Classes; Deterministic Finite Automata; Formal Languages. 
1 Introdução 
Um autômato Finito Determinístico (DFA) ou simplesmente Autômato Finito (AF) 
pode ser visto como uma máquina composta, basicamente, de três partes:[1] 
a) Fita. Dispositivo de entrada que contém a informação a ser processada; 
b) Unidade de Controle. Reflete o estado corrente da máquina 
c) Programa ou Função de Transição. Função que comanda as leituras e define o 
estado da máquina. 
 
Segundo (HOPCROFT, John E. Seattle, 7 de outubro de 1939), “as definições mais importantes dos 
termos que permeiam a teoria de autômatos, são os conceitos que incluem o alfabeto (Σ um 
conjunto de símbolos), strings (uma lista de símbolos de um alfabeto) e linguagem (um 
conjunto de strings de um mesmo alfabeto)”[2]. 
Portanto autômatos são máquinas utilizadas para tratar diversos problemas computacionais. 
Neste artigo, serão apresentados através de três classes: Estado, Transição e Autômato, a 
solução para à implementação das expressões regulares: . . . . . . . ....................... 
 
 
c) (0 + 1)* 1 (0 + 1) (0 + 1) 
b) Conjunto de todos as strings com número par de 0's e ímpar de 1's.[4] 
Estas classes foram implementadas em Java, com o intuito de explorar os recursos da 
orientação a objetos, usando deste paradigma para a construção de um simulador de 
Autômatos. 
2 Classes 
O uso do paradigma da orientação a objetos tornou mais fácil a construção e a 
manipulação das unidades necessárias para a implementação dos DFAs. As três 
classes modeladas, encapsulam os conceitos e escondem os detalhes de 
implementação, o que facilita a utilização da estrutura. 
2.1 Classe Estado 
A classe Estado (State – figura 2.1.1) é a modelagem da classe que será utilizada por 
todos os estados do DFA. A cada novo estado adicionado ao DFA, corresponderá um 
novo objeto da classe Estado que será armazenado na representação do DFA. O novo 
objeto possuirá: um identificador (id:int); o nome (name:String) do estado formado da 
junção da string “q” com o identificador; e o rótulo (label) que pode ser um 
comentário referente ao estado. 
 
Figura 2.1.1: Definição da classe Estado (State) com seus atributos e métodos. 
A seguir é mostrada a classe da figura 2.1.0 implementada em Java (Importante observar que 
não será apresentado neste artigo a implementação do comportamento dos métodos) 
public class State { 
 private int id; 
 private String name; 
 private String label; 
 public State(int id){} 
 public int getId() {} 
 public void setId(int id) {} 
 public String getName() {} 
 public void setName(String name) {} 
 public String getLabel() {} 
 public void setLabel(String label) {} 
} 
 
2.2 Classe Transição 
A classe Transição (Transition) é a modelagem da classe que será utilizada por todas 
as transições do DFA. A cada nova transição adicionada pelo usuário, corresponderá 
um novo objeto da classe transição. O novo objeto possuirá estado de origem, estado 
de destino (destiny) e símbolo (symbol). 
 
Figura 2.2.1: Definição da classe Transição (Transition) com seus atributos e métodos. 
A seguir é mostrada a classe da figura 2.2.1 implementada em Java. 
public class Transition { 
 private State origin; 
 private State destiny; 
 private String symbol; 
 public Transition(State origin, State destiny, String symbol) {} 
 public State getOrigin() {} 
 public void setOrigin(State origin) {} 
 public State getDestiny() {} 
 public void setDestiny(State destiny) {} 
 public String getSymbol() {} 
 public void setSymbol(String symbol) {} 
 public boolean equals(Object object) {} 
} 
2.3 Classe Autômato 
A classe Autômato (Automata) permite ao usuário criar e manipular 
Autômatos Finitos determinísticos utilizando as classes Estado (State) e 
Transição (Transition). Após a criação de um objeto da classe Autômato, o 
usuário poderá realizar todas as operações necessárias para a manipulação de 
Autômatos. 
 
Figura 2.3.1: Definição da classe Autômato (Automata) com seus atributos e métodos. 
A seguir é mostrada a classe da figura 2.3.1 implementada em Java. 
public class Automata { 
 private HashMap<Integer, State> states; 
 private HashMap<Integer, State> finalState; 
 private HashSet<Transition> transitions; 
 private State startState; 
 private static int startStateLimit = 0; 
 public Automata() {} 
 public void setState(int id) {} 
 public void setFinalstate(int id) {} 
 public void setStartState(int id) {} 
 public void setTransition(int origin, int destiny, String symbol) {} 
 public Transition getTransition(int origin, String symbol) {} 
 public State getStartState() {} 
 public State getFinalState(int id){} 
 public int getFinalStateSize() {} 
 public State getState(int id){} 
 public boolean isStartState(int id){} 
 public boolean isFinalState(int id) {} 
 private void message(String msg) {} 
} 
3 Expressões Regulares 
As expressões regulares oferecem algo que os autômatos não oferecem: um modo 
declarativo de expressar os strings que queremos aceitar. Dessa maneira, as 
expressões regulares servem como a linguagem de entrada para muitos sistemas que 
processam strings. Essas expressões, são outro tipo de notação para a definição de 
linguagens. 
Assumindo que o leitor já está familiarizado com o estudo de autômatos não serão 
apresentados mais detalhes sobre os assuntos abordados neste texto em relação ao que diz 
respeito a definição e funcionamento de autômatos finitos determinísticos (DFA), autômatos 
finitos não determinísticos (NFA’s), autômatos finitos não determinístico com transições ε 
(NFA- ε) e expressões regulares (ER). 
3.1 De Expressão Regular para Autômato Finito Não Determinístico (NFA) 
Dada à expressão regular c) (0 + 1)* 1 (0 + 1) (0 + 1)[4] transformar esta, em um 
NFA, utilizando dos recursos da ferramenta JFlap (www.jflap.org)[3], obtemos o 
NFA da figura 3.1.1: 
 
 
Figura 3.1.1: Conversão da Expressão Regular (0 + 1)* 1 (0 + 1) (0 + 1) em um NFA- ε. 
Como o objetivo deste artigo é implementar um DFA utilizando a linguagem Java devemos 
converter o NFA gerado na figura 3.1.1 em um DFA, tal conversão é mostrada abaixo: 
 
Figura 3.1.2 DFA gerado apartir do NFA da figura 3.1.1 
Com o resultado obtido até o momento poderíamos partir para a fase de modelagem do 
projeto. Porém a seguinte técnica pode ajudar a minimizar e a melhorar a clareza do nosso 
projeto. 
3.2 Minimizaçãode Autômatos 
Pré-requisitos para um DFA ser minimizado: 
a) Ser determinístico 
b) Não pode ter estados inacessíveis 
c) δ deve ser total (cada estado deve possuir transições para todos os elementos do 
alfabeto de entrada). Deve ser um DFA no senso estrito.[2] 
Caso o DFA não possua algum dos requisitos acima é necessário gerar um DFA equivalente. 
O resultado de minimização é mostrado na figura 3.2.3: 
 
Figura 3.2.3: Autômato minimizado gerado de acordo com as definições de minimização de 
autômatos. 
De forma análoga, utilizamos o processo de conversão mostrado acima para obter o autômato 
da figura 3.2.4 referente a expressão regular: 
b) Conjunto de todos as strings com número par de 0's e ímpar de 1's[4] 
 
 
Figura 3.2.4: Autômato minimizado gerado de acordo com as definições de minimização de 
autômatos. 
 
Após obtermos um Autômato minimizado vamos utiliza-lo para realizarmos a modelagem do 
nosso projeto. 
4 Um exemplo de utilização 
Dentre as muitas funções que o sistema oferece, foi implementada a solução para o 
DFA Minimizado da figura 3.2.3 O objetivo é determinar se o DFA reconhece a 
expressão regular: 
(0 + 1)* 1 (0 + 1) (0 + 1)[4]. 
Utilizando os recursos das classes que modelamos, podemos implementar um exemplo de 
autômato reconhecedor da expressão regular acima, a palavra a ser lida pelo nosso autômato 
de exemplo é a seguinte: “11101100100”. Começamos definindo a variável newAutomata 
que é uma instância da classe Autômato (Automata – figura 2.3.1), em seguida declaramos a 
variável que irá armazenar a string a ser reconhecida pelo autômato e fazemos uma 
verificação que finaliza o programa caso a string fornecida seja vazia pois o nosso autômato 
não reconhece strings vazias. Feitas a verificações de consistência inicial, são declaradas 
variáveis que irão manipular as nossas classes Estado(State – figura 2.1.1) e 
Transição(Transition – figura 2.2.1), feito isto precisamos definir os estados do autômato, qual 
o estado inicial e qual o conjunto de estados finais, bem como as suas respectivas transições. 
Por fim utilizando um laço enquanto (while), iteramos pela string fornecida, efetuando 
chamadas ao método da classe Transition que retorna qual o estado do autômato após ler um 
simbolo. Um exemplo da implementação deste exemplo é mostrado em seguida. 
/** 
 * Exemplo de utilização das classes Estado(State), Transição(Transition) e Autômato 
(Automata) 
 * DFA reconhecedor da expressão regular (0 + 1)* 1 (0 + 1) (0 + 1) 
 * lendo a palavra: "11101100100" 
 * @author Paulo Renato Kinjo 
 * 
 */ 
public class ExemploC { 
 
 public static void main(String[] args) { 
 // inicializa um novo autômato 
 Automata newAutomata = new Automata(); 
 // faz a leitura da palavra a ser reconhecida 
 String symbol = “11101100100”; 
 // finaliza a aplicação caso não haja entra de simbolos 
 if (symbol.isEmpty()) { 
 System.out.println("Este autômato não aceita transições vazias!"); 
 System.exit(0); 
 } 
 Transition transition; 
 State destiny; 
 // Definição dos estados do autômato 
 newAutomata.setState(0); 
 newAutomata.setState(1); 
 newAutomata.setState(2); 
 newAutomata.setState(3); 
 newAutomata.setState(4); 
 newAutomata.setState(5); 
 newAutomata.setState(6); 
 newAutomata.setState(7); 
 // Definindo qual estado é Inicial e quais são estados Finais 
 newAutomata.setStartState(0); 
 newAutomata.setFinalstate(2); 
 newAutomata.setFinalstate(4); 
 newAutomata.setFinalstate(6); 
 newAutomata.setFinalstate(7); 
 int finalStates[] = {2,4,6,7}; 
 // Definindo todas as transições do autômato 
 // (origem, destino, simbolo) 
 newAutomata.setTransition(0, 0, "0"); 
 newAutomata.setTransition(0, 1, "1"); 
 newAutomata.setTransition(1, 3, "0"); 
 newAutomata.setTransition(1, 5, "1"); 
 newAutomata.setTransition(2, 0, "0"); 
 newAutomata.setTransition(2, 1, "1"); 
 newAutomata.setTransition(3, 2, "0"); 
 newAutomata.setTransition(3, 4, "1"); 
 newAutomata.setTransition(4, 3, "0"); 
 newAutomata.setTransition(4, 5, "1"); 
 newAutomata.setTransition(5, 6, "0"); 
 newAutomata.setTransition(5, 7, "1"); 
 newAutomata.setTransition(6, 2, "0"); 
 newAutomata.setTransition(6, 4, "1"); 
 newAutomata.setTransition(7, 6, "0"); 
 newAutomata.setTransition(7, 7, "1"); 
 // uma mensagem de apresentação da aplicação 
 headerMessage(symbol, newAutomata, finalStates); 
 int i = 0; 
 int origin = 0; 
 while (i < symbol.length()) { 
 if (!(symbol.charAt(i) == ' ')) { 
 transition = newAutomata.getTransition(origin, 
 "" + symbol.charAt(i)); 
 destiny = transition.getDestiny(); 
 origin = destiny.getId(); 
 System.out.println("Leu o símbolo \"" + symbol.charAt(i) 
 + "\" foi para o \"" 
 + newAutomata.getState(origin).getName() + "\" - " 
 + newAutomata.getState(origin).getLabel()); 
 i++; 
 } else { 
 System.out.println("Este autômato não aceita transições 
vazias!!!"); 
 System.exit(0); 
 } 
 } // end while 
 // Exibe o estado em que o autômato se encontra ao final da leitura da palavra. 
 finalStateOfAutomata(symbol, newAutomata, origin); 
 } // end main 
 
 // Mensagem de apresentação da aplicação 
 public static void headerMessage(String symbol, Automata myAutomata, int 
finalStates[]) { 
 System.out.println("\nDFA reconhecedor da expressão regular 
(0+1)*1(0+1)(0+1) "); 
 
 System.out.println("Verifica a entrada \"" + symbol + "\"\n"); 
 System.out.println("Definição dos Estados:\n\t" 
 + myAutomata.getStartState().getName() + " - " 
 + myAutomata.getStartState().getLabel()); 
 for (int j = 0; j < myAutomata.getFinalStateSize(); j++) { 
 System.out.println("\n\t" + 
myAutomata.getFinalState(finalStates[j]).getName() 
 + " - " + 
myAutomata.getFinalState(finalStates[j]).getLabel() + "\n"); 
 } // for 
 } 
 // Exibe a estado final do autômato e indica o reconhecimento ou não da palavra 
fornecida. 
 public static void finalStateOfAutomata(String symbol, Automata myAutomata, 
 int origin) { 
 if (myAutomata.isFinalState(origin)) { 
 System.out.println("\nA entrada \"" + symbol 
 + "\" foi aceita !!!\n"); 
 } else { 
 System.out.println("\nA entrada \"" + symbol 
 + "\" foi rejeitada !!!\n"); 
 } 
 } 
} // class 
Ao final o sistema ira mostrar a frase: “A entrada 11101100100 foi aceita!!!” para a palavra 
utilizada neste exemplo. 
DFA reconhecedor da expressão regular (0+1)*1(0+1)(0+1) 
Verifica a entrada "11101100100" 
 
Definição dos Estados: 
 Estado Inicial - q0 
 Estado Final - q2 
 Estado Final - q4 
 Estado Final - q6 
 Estado Final - q7 
 
Leu o símbolo "1" foi para o "Estado Simples" - q1 
Leu o símbolo "1" foi para o "Estado Simples" - q5 
Leu o símbolo "1" foi para o "Estado Final" - q7 
Leu o símbolo "0" foi para o "Estado Final" - q6 
Leu o símbolo "1" foi para o "Estado Final" - q4 
Leu o símbolo "1" foi para o "Estado Simples" - q5 
Leu o símbolo "0" foi para o "Estado Final" - q6 
Leu o símbolo "0" foi para o "Estado Final" - q2 
Leu o símbolo "1" foi para o "Estado Simples" - q1 
Leu o símbolo "0" foi para o "Estado Simples" - q3 
Leu o símbolo "0" foi para o "Estado Final" - q2 
 
A entrada "11101100100" foi aceita !!! 
 
Observe que apenas modificando as definições de estados e transições do autômato 
implementado no exemplo acima, podemos definir o autômato da figura 3.2.4 que lêndo a 
mesma mensagem (11101100100) declarada no exemplo anterior, aprensentaria a mensagem:A entrada "11101100100" foi rejeitada !!! 
 
5 Conclusão 
Na prática, aplicações de DFAs podem ser tediosas, principalmente quando os DFAs 
são muitos grandes. As 3 classes implementadas auxiliam desenvolvedores de 
aplicações que utilizam DFAs, pois tornam mais simples sua manipulação. A classe 
Autômato (Automata) por possuir métodos que manipulam os estados e as transições 
do autômato claramente apresenta uma maior complexidade no seu desenvolvimento. 
Tendo como objetivo a implementação de um DFA não houve motivos para se 
preocupar com o desenvolvimento de métodos (comportamentos) mais robustos que 
possam implementar autômatos finitos não determinísticos (NFAs), mas podemos 
observar que para que possamos aplicar esta melhora em nosso projeto teríamos que 
realizar pequenas mudanças em uma ou outra classe, mantendo a estrutura do projeto 
sem grandes mudanças. 
6 Referências 
[1] MENEZES, Paulo B. Linguagens Formais e Autômatos. 4 ed. Porto Alegre: Sagra-
Luzzatto, 2001. 165p. 
[2] HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introdução à teoria de 
autômatos, linguagens e computação. Rio de Janeiro: Elsevier, 2003. 560 p. 
[3] http://www.jflap.org 
[4] 4642C-04 – Linguagens Formais – Turma 128 – 2012/2 – Prof. Flavio Oliveira. Notas de 
Aulas e Trabalho(T1)