AULA 4: AUTOMATOS FINITOS 
=========================

- inicio do estudo de maquinas abstratas -- que servirao para definir
formalmente o que e' um procedimento efetivo (ou computavel).
Comecamos com uma maquina simples (automato finito - reconhece as linguagens
regulares), depois automato a pilha (reconhece as linguagens livres de
contexto), e finalmente maquina de Turing (prototipo teorico das funcoes
"computaveis).

Def: um procedimento EFETIVO e' um processo discreto e deterministico que
termina para todos os valores de entrada possiveis.

- Gramatica : pode ser visto como "geradores" de palavras de uma linguagem
  Maquina:    pode ser visto como "reconhecedor" de palavras de uma ling.

EXEMPLO de Maquina de estado finito:
  - problema: um homem, um leao, um coelho e um repolho devem atravessar um
rio usando um canoa, com a retricao de que o homem deve transportar no
maximo um dos tres de cada vez de uma margem a outra.  Alem disso, o leao
nao pode ficar na mesma margem que o coelho sem a presenca do homem, e o
coelho nao pode ficar com o repolho sem a presenca do homem.  O problema
consiste em determinar se e' possivel fazer a travessia.

  Entrada: uma sequencia de letras:  c-coelho, l-leao, r-repolho e s-sozinho.
           Ex: cls  : c = homem leva coelho da direita p/ esquerda
                      l = homem leva leao da esquerda p/ direita
                      s = homem volta para esquerda sozinho
  Saida:   aceita - se todos atravessam o rio seguindo as restricoes acima
           rejeita - caso contrario

  Estados: os que estao na margem inicial {h,l,c,r}.  Se o homem atravessa
           para a outra margem com o leao, vamos para o estado {c,r}.
           O estado final e' {}, ou seja, todos atravessaram para a outra
           margem.   A transicao de um estado para outro deve respeitar as
           restricoes impostas no enunciado do problema

  Diagrama de estados:























  - existe um conjunto infinito de solucoes, mas duas solucoes de tamanho
minimo: cslcrsc e csrclsc
  - processamento de uma palavra w=xy.  Apos processado o string x, para
continuar o processamento, basta saber:
    1) o estado atual
    2) y

  - este par determina a configuracao instantanea da maquina (fotografia do
estado atual).  A relacao |- permite mostrar a evolucao das configuracoes
durante o processamento de uma palavra.  [e1, w] |- [e2,y] se existe uma
transicao de e1 para e2 sob a e w=ay.   Exemplo:
   [{l,r}, sllr] |- [{h,l,r},llr] |- [{r},lr] |- [{h,l,r},r] |- [{l}, epsilon]

  - caracteristicas do diagrama acima:
    1) determinismo: nao existe mais de uma transicao partindo de um estado
sob o mesmo simbolo
    2) apenas um estado final
    3) numero de estados finito

DEF: AUTOMATO FINITO DETERMINISTICO (AFD): um AFD e' uma quintupla
(Q, Sigma, Delta, q0, F), onde:
Q e' um conjunto finito de estados
Sigma e' um alfabeto (simbolos terminais)
Delta e' a funcao TOTAL de transicao QxSigma -> Q  (condicao de DETERMINISMO)
q0 e' o estado inicial, q0 pertence a Q
F  e' o conjunto de estados finais, F subconjunto de Q

Exemplo:  
   - diagrama (note a existencia de estado de erro):








   - tabela de transicao:








   - simulacao de uma computacao usando fita de entrada e o estado atual:








DEF: a configuracao instantanea de uma maquina e' um par ordenado [qi, w],
onde qi e' o estado atual, e w pertencente a Sigma* e' a parte do string de
entrada ainda nao processado.

DEF: A relacao |-M (resulta) e' definida por:
  [qi, aw] |-M [delta(qi,a), w], 
onde a pertence a Sigma, w pertence a Sigma* e delta e' a funcao de
trasicao de M.

A funcao |- permite mostrar a evolucao das configuracoes durante o
processamento de uma palavra.  

Exemplo (usando o automato do exemplo anterior):
   [q0,aabba] |- [q1,abba] |- [q1,bba] |- [q0,ba] |- [q0,a] |- [q1,epsilon]

DEF:  a funcao de transicao estendida delta^de uma funcao de transicao
delta e' uma funcao de (QxSigma*) para Q definida recursivamente como:
  1) se |w| = 0, entao w = epsilon e delta^(qi,epsilon) = qi
     se |w| = 1, entao w = a (a pertence a Sigma) e delta^(qi,a) = delta(qi,a)
  2) se |w| > 1, entao w = ua e delta^(qi,ua) = delta(delta^(qi,u), a)


EXEMPLOS:
0) 0 (0+1)*

1) (0+1)* 1

3) {w em {a,b}* | w possui dois b's consecutivos}

4) {w em {a,b}* | w nao possui dois a's consecutivos}

5) {w em {a,b}* | |w| e' par}

6) {w em {a,b}* | w possui numero par de a's e impar de b's}

7) {w em {0,1,2,3}* | a soma dos simbolos e' divisivel por 4}

O DIAGRAMA DE ESTADOS SIMPLIFICADO  e' aquele que reconhece a mesma
linguagem, sem a existencia do estado de erro.

8) (ab)*c