Autômatos

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.
Passos
1. 1

Comece criando um FA ou usando um fornecido como exercício. O FA da figura vai servir de exemplo. 2. 2
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ó. 3. 3
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. 4. 4
Escolha um novo estado para remover. 5. 5
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. 6. 6

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. 7. 7

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