EVENTOS CRIATIVOS
Autômatos Finitos, o que são?
Autômatos finitos, ou sistema de estados finitos, são modelos usados para representar o funcionamento de maquinas ou sistemas autônomos utilizados em diversas aplicações do cotidiano, como portas automáticas, elevadores, maquinas de refrigerante, algoritmos, circuitos lógicos e, como será o foco desse estudo, reconhecedores de linguagens regulares.
Pode-se definir um autômato finito como uma quíntupla (S, Σ, δ, s0, F), onde temos:
-S: conjunto finito, não vazio, dos estados possíveis.
-Σ: conjunto, não vazio, que constitui o alfabeto do autômato.
-δ: função de transição.
-s0: estado inicial.
-F: conjunto dos estados finais.
O modo mais simples de se entender autômatos finitos é por meio da representação visual de seus estados e transições. Como exemplo, considere o seguinte autômato: A=({q0,q1}, {0,1}, δ, q0, {q1}), onde
δ(q0,0)=q1, δ(q0,1)=q0, δ(q1,0)=q1 e δ(q1,1)=q0
Esse autômato pode ser representado pelo seguinte diagrama:
Com os arcos representando as transições entre os estados, representados pelos círculos. Neste esquema temos que o triângulo indica qual é o estado inicial (q0) e o estado final é denotado por dois círculos concêntricos.
Na Prática:
Para esclarecer o uso dos autômatos finitos na representação do funcionamento de sistemas do dia-a-dia peguemos, por exemplo, um sistema de alarme de carro:
Também podemos usar autômatos finitos para construir reconhecedores de linguagens regulares.
Exemplo: o autômato do primeiro exemplo gera a linguagem regular L = (0|1)*0 e podemos usá-lo para o reconhecimento de cadeias binárias.
Peguemos por exemplo a cadeia A = 10110.
Usando as funçoes de transição δ obtemos a seguinte tabela:
A tabela mostra as transções que ocorrem conforme a cadeia é inserida no autômato. Note que o primeiro estado atual é o estado inicial do autômato e a cadeia pertence a linguagem L se o último estado da tabela é o estado final do autômato. Como q1 é o estado final do autômato em questão a cadeia A pertence a linguagem L.
Automatos Finitos Determinísticos (AFD) e Não-Determinísticos (AFND):
Automatos finitos são categorizados como determinísticos ou não-determinísticos.
Os AFD têm a característica de que, dado um estado atual "q" e um caractere de entrada "x", tem-se no máximo um estado possível para transição, ou seja, para cada cadeia de caracteres há um único caminho a ser seguido no autômato.
Nos AFND pode-se ter funções de transição do tipo δ(q,x) = {a,b}, onde a e b são dois estados possíveis de se chegar através do estado q, por meio da entrada do caractere x. As funções de transição dos AFD são da forma δ : Q × Σ → Q, com Q sendo o conjunto finito de estados e Σ sendo o conjunto finito com os símbolos de entrada, ou Alfabeto.
Nos AFND as funções de transição têm a forma δ : Q × Σ → P(Q), onde P(Q) denota o conjunto das partes de Q, que nada mais é do que o conjunto de todos os subconjuntos de Q. Por exemplo:
Sendo T = {a,b,c}, um conjunto com 3 elementos, P(T) = { {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }
Ou seja, nos AFND pode-se ter, dado um estado atual, mais de uma transição para outros estados que consomem o mesmo caractere da cadeia de entrada.
Exemplo de AFND:
Os AFD e AFND são equivalentes, ou seja, dado o AFND é possível construir um AFD equivalente (ambos reconhecem a mesma linguagem regular) e vice-versa.
Isso nos diz que os AFND são incapazes de reconhecer alguma linguagem que não pode ser reconhecida por algum AFD, portanto, como os AFD reconhecer apenas linguagens regulares, os AFND também são restritos ao reconhecimento destas.
AFND-λ
Um tipo de AFND são os AFND com λ-movimentos (ou AFND-λ). Estes tem a característica de permitirem a transição de um estado para outro sem o consumo de nenhum caractere da cadeia de entrada. São as chamadas transições λ.
A única diferença entre os AFND e os AFND-λ são as funções de transição. As funções dos AFND-λ tem a forma δ : Q × (Σ ∪ {λ}) → P (Q). Perceba que são muito parecidas com as dos AFND, apenas com a inclusão da possibilidade de transitar de estados com o elemento vazio λ.
Exemplo:
Seja M um AFND-λ que determina se a entrada contém um número par de “0” ou um número par de “1”.
M = ( {q0, q1, q2, q3, q4, q5 }, {0, 1}, δ, q0, {q1, q2} )
O AFND-λ M é representado no seguinte diagrama:
O AFND-λ M pode ser visto como a unição de dois AFDs: um com os estados {q1, q3} e outro com os estados {q2, q4} e a linguagem de M pode ser descrita pela uniao da linguagem dos dois AFDs.
Sem ler nenhuma entrada o AF com movimentos nulos pode mudar de qo para q1 ou q2. Ou seja, a união de autômatos finitos é um AFND por definição. Observe que, ao começar o reconhecimento de uma cadeia, encontramos uma ambiguidade: não se sabe se o sistema está no estado q0, q1 ou q2.
Equivalencias:
Assim como já foi dito antes, os AFD e os AFND podem ser equivalentes. O mesmo acontece entre os AFND e os AFND-λ, ou seja, é possível construir um AFND-λ que reconheça a mesma linguagem que qualquer AFND e vice-versa.
Sendo assim, podemos dizer que os AFD, os AFND e os AFND-λ podem ser equivalentes entre si, isto é, é possível transformar um no outro onde todos reconhecem a mesma linguagem regular.
Mas as equivalências não param por ai. Mostraremos como é possível obter um AF a partir da Gramática Regular.
Da GR ao AFND-λ:
Suponha G = (V,T,P,S) uma GR.
É possível criar o AFND-λ M = (Q,Σ,δ,q0,F) que simula as derivações de G com:
Σ = T
Q = V + {qf}
F = {qf}
q0 = S
E traduzimos as regras de produção para as funções de transição da seguinte forma:
A → λ => δ(A,λ) = qf
A → a => δ(A,a) = qf
A → aB => δ(A,a) = B
Pronto! obtemos nosso AFND-λ a partir de uma GR.
Como toda linguagem regular vem de uma Gramática Regular, pode ser representada por um Autômato Finito e pode ser escrita por uma Expressão Regular nós chegamos a conclusão que GRs, ERs e AFs são todos equivalêntes!
Referencias:
https://en.wikipedia.org/wiki/Deterministic_finite_automaton
http://www.dcc.fc.up.pt/~rvr/resources/MC10/automatos1.pdf
http://www.cin.ufpe.br/~agsf/disciplinas/sistemas_digitais/aula19_MaquinasEstadosFinitos.pdf
