Como Converter um Autômato Finito em Expressão Regular - wikiHow

Prévia do material em texto

Editar
1
2
3
4
5
Como Converter um Autômato Finito em
Expressão Regular
Autômatos finitos (FA - Finite Automata) pertencem a um modelo matemático capaz de reconhecer
cadeias de linguagens regulares. O estudo dos FA é parte importante dos fundamentos da teoria da
computação. O modelo capaz de gerar cadeias de linguagens regulares são as expressões
regulares (RE - Regular Expressions) (as mesmas usadas em diversas linguagens de programação,
como Java). Agora, iremos aprender como converter um FA em uma RE.
Comece criando um FA ou
usando um fornecido como
exercício. O FA da figura vai
servir de exemplo.
O procedimento consiste em remover um a um os estados do FA, substituindo o
estado removido por novas transições cujos rótulos são os rótulos das transições
de todos os possíveis caminhos passando por aquele nó.
Escolha um dos estados para "colapsar". No nosso exemplo, q2 foi escolhido.
Verifique quais são os caminhos possíveis passando por aquele nó. Crie novas
transições ligando os estados remanescentes como descrito acima. No exemplo,
criaremos uma transição ligando q0 a q1 com rótulo 00 e de q0 a q3 com rótulo 01.
Verifique no novo autômato se as novas
transições realmente representam os
caminhos removidos.
Escolha um novo estado para remover.
Escolha outro estado para remover. No exemplo, removeremos agora q3.
Novamente crie novas transições representando os caminhos passando por aquele
estado. Foi criada uma transição entre q0 e q4 com rótulo 001 e entre q1 e q4 com
rótulo 01.
Passos
como fazer qualquer coisa
Como Converter um Autômato Finito em Expressão Regular - wikiHow http://pt.wikihow.com/Converter-um-Autômato-Finito-em-Expressão-R...
1 de 2 14/10/2012 19:44
6
7
Algumas vezes, você precisa
representar caminhos circulares
usando a operação de fecho de Kleene
(* - asterisco) e fazer passos
intermediários. Na figura, os caminhos
entre q0 e q4 que passavam por q1 foram
convertidos para transições.
Continue a remover os
estados, até que sobre
somente um estado inicial e um
estado final. Escreva a
expressão regular representando
os laços com operações de fecho.
A expressão regular: ( (00+1)(1*01)+001 )(01*01)*
Tente começar pelos estados que tenham o menor número de caminhos. Pode ocorrer uma
explosão combinatória se você tentar remover um estado muito "ativo" antes.
Algumas vezes as expressões regulares resultantes podem parecer muito complexas. E na
maioria das vezes elas podem ser simplificadas.
O JFLAP pode converter FA em RE automaticamente. Ele segue um outro método (usando
transições por lambda), e as RE que ele gera não são otimizadas.
Dicas
Como Converter um Autômato Finito em Expressão Regular - wikiHow http://pt.wikihow.com/Converter-um-Autômato-Finito-em-Expressão-R...
2 de 2 14/10/2012 19:44