Capítulo 2 Parte I AFD's

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
2. Máquinas de Estados Finitos
Parte I
*
*
As máquinas de estado-finito são máquinas abstratas que capturam as partes essenciais de algumas máquinas concretas.
Estas ultimas vão desde máquinas de vender jornais e de vender refrigerantes, passando por relógios digitais e elevadores, até programas de computador, como alguns procedimentos de editores de textos e de compiladores. 
O próprio computador digital, se considerarmos que sua memória é limitada, pode ser modelado por meio de uma máquina de estado-finito.
Existem, basicamente, dois tipos de máquinas de estado-finito: os transdutores e os reconhecedores (ou aceitadores) de linguagens. 
Os transdutores são máquinas com entrada e saída, e os reconhecedores são máquinas com apenas duas saídas possíveis; usualmente, uma delas significa “aceitação” da entrada, e a outra, “rejeição” da entrada.
2.1. Introdução
*
*
As linguagens reconhecidas por máquinas de estado-finito são denominadas linguagens regulares.
Uma característica fundamental de uma máquina de estado-finito é que sua memória é limitada e exclusivamente organizada em torno do conceito de “estado”.
As máquinas de estado-finito do tipo reconhecedor de linguagem são mais conhecidas como autômatos finitos. 
Os transdutores são também conhecidos como autômatos finitos com saída.
2.1. Introdução
*
*
Exemplo: Um homem, um leão, um coelho e um repolho devem atravessar um rio usando uma canoa, com a restrição de que o homem deve transportar no máximo um dos três de cada vez de uma margem à outra. Além disso, o leão não pode ficar na mesma margem que o coelho sem a presença do homem, e o coelho não pode ficar com o repolho sem a presença do homem. O problema consiste em determinar se é possível fazer a travessia.
A solução de qualquer problema é sempre, ou deveria ser, antecedida por uma fase de modelagem, na qual:
(a) as informações relevantes, que efetivamente têm influência na solução do problema, são identificadas, deixando-se de lado aquelas que não contribuem para a solução;
(b) as informações relevantes são estruturadas (ou seja, representadas), de forma a facilitar a posterior solução).
Abstração: processo de identificar as informações relevantes e desprezar as que não têm relevância.
2.1. Introdução
*
*
Para o problema proposto, pode-se identificar como informações relevantes:
(a) em um dado instante, em que margem do rio estão o homem, o leão, o coelho, e o repolho;
(b) a sequencia de movimentações entre as margens que propiciou a situação indicada em (a).
Observe a “economia”: não é necessário dizer em que margem está a canoa, pois ela estará onde o homem estiver; não é necessário representar uma situação em que a canoa está no meio do rio, pois isto não é importante para se chegar à solução, etc. 
2.1. Introdução
*
*
A primeira informação pode ser representada escrevendo-se apenas o que está na margem esquerda, pois o resto estará na margem direita. 
Por exemplo, usando as letras h, significando “homem”, l, significando “leão, c, significando “coelho” e r, significando “repolho”, tal informação poderia ser dada por um conjunto contendo elementos de {h, l, c, r}. 
Por exemplo, {h, c, r} representa a situação em que o homem, o coelho e o repolho estão na margem esquerda e o leão na margem direita; {r} representa o repolho na margem esquerda e o homem, coelho e leão na margem direita.
2.1. Introdução
*
*
A segunda informação importante para o problema, sequencia de movimentações, pode ser representada por uma palavra a0a1a2 . . . an, onde cada ai pode ser s, l, c ou r. 
Supondo que todos estão na margem esquerda no início, tem-se que ai denota movimentação da esquerda para a direita se i é par e denota movimentação da direita para a esquerda se i é impar. 
Se ai é s, o homem está indo sozinho; se é l, está levando o leão; se é c, está levando o coelho; e se é r, está levando o repolho. 
Por exemplo, a palavra csr representa uma movimentação em que:
1) a0 = c: o homem leva o coelho da esquerda para a direita.
2) a1 = s: o homem volta sozinho da direita para a esquerda.
3) a2 = r: o homem leva o repolho da esquerda para a direita.
2.1. Introdução
*
*
Observe que cada uma das situações deste exemplo, descrita por um conjunto, é uma “fotografia” dos elementos relevantes da realidade que estamos modelando. 
Tal fotografia é, em alguns contextos, denominada estado. 
Um estado pode ser imaginado como uma representação dos elementos essenciais de uma realidade que estamos modelando, sendo que a escolha dos elementos essenciais depende da aplicação. 
Já cada elemento da palavra que representa uma sequência de movimentações especifica uma operação que propicia a transição de um estado para outro. 
Assim, o problema pode ser visto como “encontrar uma palavra que represente uma sequência de transições que leve de um estado inicial ({h, l, c, r}, no exemplo) a um estado final {}”.
2.1. Introdução
*
*
Nesta figura, cada estado é representado por uma oval e cada transição possível é representada por uma seta ligando o estado ao qual ela se aplica ao estado que resulta de sua aplicação. 
O estado inicial é ressaltado por meio de uma seta que o aponta e o estado final é ressaltado por meio de uma oval dupla.
2.1. Introdução
*
*
Se existe uma aresta de e1 para e2 com rótulo a no diagrama de estados, será dito que existe uma transição de e1 para e2 sob a.
O conjunto de todas as soluções para o problema é o conjunto das palavras correspondentes aos caminhos do estado inicial ao estado final.
Cada palavra é formada concatenando-se os rótulos das arestas percorridas no caminho do estado inicial ao estado final. 
Pelo esquema, fica claro que existe um conjunto infinito de soluções e que existem duas soluções de tamanho mínimo: cslcrsc e csrclsc. 
Dada uma palavra w de {s, l, c, r}* como saber se w é solução?
Deve-se verificar o caminho correspondente; uma w partindo do estado inicial chega ao estado final? Caso afirmativo, w é solução, caso contrário, não. 
No primeiro caso diz-se que w é reconhecida ou aceita e no segundo diz-se que w é rejeitada. 
2.1. Introdução
*
*
Suponha que x seja um prefixo de w, ou seja, w = xy, para alguma palavra y. No processo de verificar se w é reconhecida, quando tiver terminado o processamento de x, o que é necessário para continuar o processo? 
Apenas duas informações; o estado atual e y.
Este par é denominado configuração instantânea. Uma notação útil é a associada a |- (resulta em), que permite mostrar, passo a passo, a evolução da configurações instantâneas durante o processamento de uma palavra. 
Diz-se que [e1, w] |- [e2, y] se existe uma transição de e1 para e2 sob a e w = ay. Assim, por exemplo:
Esta cadeia de relacionamentos pode ser interpretada como uma computação (da máquina cujo diagrama foi apresentado) iniciada no estado {l, r} processando sllr. 
2.1. Introdução
*
*
Na máquina apresentada, a toda transição do estado e1 para e2 existe uma transição inversa do estado e2 para e1 sob o mesmo símbolo. Esta característica não está presente em todos os diagramas de estado. 
Outra característica nem sempre presente é a ocorrência de um único estado final. 
Outra característica é que para cada par (estado símbolo) existe, no máximo, uma transição, ou seja, se existe uma transição de e1 para e2 sob a, então não existe outra transição de e1 para qualquer outro estado sob a. 
Esta característica confere um caráter de determinismo à máquina abstrata: dada uma palavra w, existe um único estado que pode ser atingido a partir de qualquer estado, processando-se w. 
Uma característica compartilhada por qualquer autômato finito é que o número de estados é finito. 
2.1. Introdução
*
*
Um AFD é uma máquina abstrata constituída de três entidades:
Um conjunto de estados.
Um alfabeto.
Um conjunto de transições (definidos como uma função). 
Esta definição modela as transições de um AFD como
uma função que mapeia cada par (estado, símbolo) para um estado que caracteriza o determinismo do AFD (cada par estado-símbolo leva a um único estado): a partir do estado inicial, só é possível atingir um único estado para uma dada palavra de entrada. 
2.2. Autômatos Finitos Determinísticos
*
*
*
*
*
*
Defini-se, a seguir, uma função que dado um estado e uma palavra w, retorna o estado alcançado. Evidentemente, ela deve coincidir com a função de transição para palavras de tamanho 1). 
Utilizando-se  (chapéu) pode-se definir a linguagem reconhecida ou aceita por um AFD.
2.2. Autômatos Finitos Determinísticos
*
*
Assim, a linguagem aceita pelo AFD do primeiro exemplo é o conjunto de todas as palavras que representam sequências de movimentos que propiciam o transporte seguro dos elementos citados.
Em princípio, pode-se pensar em implementar um dado AFD, visto como reconhecedor, nas mais diversas tecnologias, inclusive via um procedimento. 
Neste último caso, pode-se usar qualquer paradigma de programação.
Procedimento para um AFD – Variáveis:
Assume-se a existência de um procedimento do tipo função, prox , que retorna o próximo símbolo de entrada, quando houver, e fs (fim de sequencia), quando não houver. 
O tempo de execução diretamente proporcional ao tamanho da palavra de entrada.
2.2. Autômatos Finitos Determinísticos
*
*
Exemplo: será apresentado um AFD M tal que: L(M) = {w  {0,1}* | |w| é par}.
Após ter lido um prefixo x de uma palavra, o que se deve saber para prosseguir no seu reconhecimento? Apenas se x tem um número par ou impar de símbolos. Assim, o autômato terá apenas dois estados: par ou impar. 
2.2. Autômatos Finitos Determinísticos
*
*
Exemplo: será apresentado um AFD N tal que: L(N) = { w  {0,1}* | w tem um número par de 0s e um número par de 1s}
Após um prefixo, deve-se saber se o número de 0s é par ou impar e se o número de 1s é par ou impar para que se tenha controle da paridade de ambos os dígitos o tempo todo. 
O estado pp representa a situação em que o número de 0s e 1s é par, pi corresponde a situação em que o número de 0s é par e 1s é impar e assim por diante.
Se este autômato tivesse como estados finais os estados pp e ii, ele aceitaria a mesma linguagem que o AFD do exemplo anterior. É fácil perceber que se uma linguagem pode ser reconhecida por AFD’s, então ela pode ser reconhecida por inúmeros AFD’s.
*
*
*
*
Dado que podem existir vários AFDs equivalentes para uma linguagem, tem sentido indagar se existiria um AFD “mínimo” para uma linguagem. 
Se for assumido um alfabeto mínimo (sem símbolos inúteis), existem duas entidades que influenciam o tamanho de um AFD: os números de estados e de transições. 
Como a função de transição é total, o número de transições é apenas função do número de estados: quanto menos estados, menos transições. 
Ou seja, tem sentido dizer que um AFD para reconhecer uma linguagem é mínimo se nenhum outro que reconheça a mesma linguagem tem um número de estados menor. 
*
*
Estudar a seção 2.2.3 – Algumas Propriedades dos AFDs (apenas páginas 75, 76, e 77).
Entender e explicar melhor o teorema (pág. 76) abaixo, mostrando como obter as linguagens (explicar melhor os exemplos que ilustram a aplicação do teorema):
TRABALHO: realizar em dupla
*
*
Para toda linguagem finita, sempre existe um AFD que a reconhece.
Exemplo: L(M) = {001, 101, 0001}
Se uma linguagem é finita, sempre existe um AFD que a reconhece. 
Existem AFD que reconhecem a linguagem, cujo diagrama de estado simplificado não contém ciclos.
Por outro lado, se um diagrama de estados de um AFD não contém ciclos, então a linguagem que tal AFD reconhece é finita.
*
*
Assim, uma linguagem L é infinita se, e somente se:
Não existe AFD que reconhece L; ou
O diagrama de estados de qualquer AFD que reconheça L contém ciclo.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*