Para ver a primeira parte clique aqui
Linguagens Regulares – Sistemas de Estados Finitos:
Um Sistema de Estados Finitos é um modelo matemático de sistema com entradase e saídas discretas. Pode assumir um número finito e pré-definido de estados. Cada estado resume somente as informações do passado necessárias para determinar as ações para a próxima entrada.
Autômato Finito – AFD (Autômato Finito Determinístico) é uma 5-upla:
é um conjunto finito não vazio de estados do autômato;
é um conjunto de símbolos, denominado alfabeto de entrada do autômato;
é a função de transição de estados do autômato e seu papel é o de indicar as transições possíveis em cada configuração do autômato. Esta função fornece para cada par “estado e símbolo de entrada” um novo estado para onde o autômato deverá mover-se.
é denominado estado inicial do autômato finito. É o estado para o qual o reconhecedor deve ser levado antes de iniciar suas atividades.
é um subconjunto do conjunto Q dos estados do autômato, e contém todos os estados de aceitação ou estados finais do autômato finito. Estes estados são aqueles em que o autômato deve terminar o reconhecimento das cadeias de entrada que pertencem à linguagem que o autômato define. Nenhuma outra cadeia deve ser capaz de levar o autômato a qualquer destes estados.
Autômato Finito Não-Determinístico (AFN) – Autômatos finitos não determinísticos diferem dos Autômatos finitos determinísticos quanto à regra de transição entre estados. Dada uma combinação de um estado atual e um símbolo de entrada, pode não haver estados especificados para os quais o estado atual deve conduzir o processamento, bem como pode haver vários estados resultantes da leitura do símbolo. Portanto, para uma função de transição ? definida em 
, o seu valor não deve ser um elemento de Q (como acontece com os autômatos determinísticos), mas um subconjunto de Q (incluindo o conjunto vazio). Ou seja, o processamento de 
leva à um conjunto de estados em que a máquina pode legalmente se encontrar após estar em um estado q lendo um símbolo de entrada a.
Equivalência entre AFD e AFN – Embora um AFN seja somente um acréscimo ao AFD, na verdade não aumenta seu poder computacional, sendo assim, para cada AFN é possível construir um AFD equivalente que realiza o mesmo processamento. O contrário também é verdadeiro.
Autômato Finito com Movimentos Vazios – Movimentos vazios constituem uma generalização dos modelos de máquinas não-determinística, é um movimento determinado por uma simples mudança de estado. Uma das vantagens dos autômatos Finitos com Movimentos Vazios no estudo das linguagens Formais é o fato de facilitar algumas construções e demonstrações relacionadas com os autômatos.
Equivalência entre AFN e AFe – Analogamente ao não-determinístico, os movimentos vazios não aumentam o poder computacional dos autõmatos finitos. Assim, para cada AFe, é possível construir um AFN que realiza o mesmo processamento. O contrário é trivialmente verdadeiro.
Minimização de um autômato Finito
– Alguns autômatos possuem estados que são funcionalmente os mesmos. O algorítmo de minimização tem como objetivo unir estes estados em um único.
Pré-requisitos do algorítmo de Minimização
- O autômato deve ser determinístico;
- Todos os estudos devem ser alcançados iniciando do estado inicial;
Algorítmo
- Construa uma tabela, marcando os elementos que são por definição funcionalmente diferentes (estado inicial e final)
- Dois a dois, os outros estados marcados e que são funcionalmente diferentes.
- Unir os estados equivalentes.
Com estes conceitos básicos podemos passar para o estudo das Expressões Regulares
, o seu valor não deve ser um elemento de Q (como acontece com os autômatos determinísticos), mas um subconjunto de Q (incluindo o conjunto vazio). Ou seja, o processamento de leva à um conjunto de estados em que a máquina pode legalmente se encontrar após estar em um estado q lendo um símbolo de entrada a. Assim, podemos definir um autômato finito não determinístico matematicamente como se segue.