Autômatos Finitos em aplicações práticas

Prévia do material em texto

UNIVERSIDADE FEDERAL DE OURO PRETO - UFOP 
Instituto de Ciências Exatas e Aplicadas – João Monlevade 
DECSI 
 
Carlos B. Alexandre Júnior 15.2.81.24 
Douglas Mendes Vieira 15.1.8286 
Emily Ferreira de Brito 15.2.8030 
Fernando Aparecido da Silva 15.1.8291 
Suzane Ferreira Pinto 15.2.5923 
 
 
 
 
 
 
Autômatos Finitos em aplicações práticas 
 
 
 
 
 
 
Trabalho apresentado à disciplina de 
Fundamentos Teóricos da Computação, com o 
objetivo de demonstrar aplicações práticas dos 
Autômatos Finitos. 
Professor: Fabianni Roberto Teles 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
João Monlevade 
Outubro/2018 
UNIVERSIDADE FEDERAL DE OURO PRETO - UFOP 
Instituto de Ciências Exatas e Aplicadas – João Monlevade 
DECSI 
 
Modelagem de um quebra-cabeça 
 
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 e, caso seja, uma 
sequência de movimentações que propicie 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 de forma a facilitar a posterior solução. 
 
Essas duas etapas não precisam ocorrer nessa ordem, sendo comum as duas serem 
consideradas simultaneamente. E, de modo geral, quanto “menos” informações se capturar 
da realidade que se está modelando, mais fácil e/ou eficiente se tornará a etapa de solução. 
Esse processo de identificar as informações relevantes e desprezar as que não tem relevância 
é denominado abstração. Assim, por exemplo, quando se diz que um autômato finito é uma 
máquina abstrata, está-se dizendo que ele expressa a parte essencial, desprezando-se os 
detalhes de implementação que, no presente contexto, são considerados irrelevantes. 
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 sequência de movimentações entre as margens que propiciou a situação indicada em (a) 
 
A primeira informação pode ser explicitada anotando-se o que está na margem de 
partida e o que está na margem de destino. Assim, usando as letras h, significando “homem”; 
l, “leão”; c, “coelho”; e r, “repolho”, tal informação poderia ser dada por dois subconjuntos de 
{h, l, c, r}. Por exemplo, {h, c, r}/{l} representa a situação em que o homem, o coelho e o repolho 
estão na margem de partida e o leão na margem de destino; {r}/{h, l, c} representa o repolho 
na margem de partida e o homem, o coelho e o leão na margem de destino. A segunda 
informação importante para o problema, sequência de movimentações, pode ser explicitada 
por uma palavra a1a2 . . . an, em que cada ai pode ser s, l, c ou r. Um certo ai denota 
movimentação da margem de partida para a de destino se i for ímpar e denota movimentação 
no sentido contrário se i for par. Se ai for: s, o homem estará indo sozinho; l, estará levando o 
leão; c, estará levando o coelho; e r, estará levando o repolho. Por exemplo, a palavra csr 
representa uma movimentação em que: 
 
1. a1 = c: o homem leva o coelho da margem de partida para a de destino; 
2. a2 = s: o homem volta sozinho da margem de destino para a de partida; e 
3. a3 = r: o homem leva o repolho da margem de partida para a de destino. 
 
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 (∅/{h, l, c, r}, no exemplo)”. 
 
Dada uma palavra w de {s, l, c, r} ∗, como saber se w é uma solução? 
 
 Verifica se o “caminho correspondente” a w partindo do estado inicial chega ao estado 
final; 
UNIVERSIDADE FEDERAL DE OURO PRETO - UFOP 
Instituto de Ciências Exatas e Aplicadas – João Monlevade 
DECSI 
 
 Se chegar, diz-se que w é reconhecida, ou aceita, caso contrário, diz-se que não é 
reconhecida, e sim rejeitada. 
 
Está apresentada na figura abaixo uma representação gráfica do espaço dos estados 
e transições possíveis para o exemplo, mediante o que se denomina diagrama de estados. 
Nessa 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. Para simplificar a figura, e também a exposição a seguir, um subconjunto de 
{h, l, c, r} ´e representado pela sequência de seus elementos na ordem h, l, c, r; o conjunto 
vazio é representado por ∅ mesmo. O estado inicial é ressaltado por meio de uma seta que o 
aponta e o estado final é ressaltado por meio de uma oval dupla. Mais precisamente, o espaço 
de estados e transições pode ser modelado por meio de um grafo dirigido em que os vértices 
são os estados, as arestas são as transições, e que tem dois vértices destacados como inicial 
e final. Se existe uma aresta de e1 para e2 com rótulo a no diagrama de estados, será dito 
que há uma transição de e1 para e2 sob a. O conjunto de todas as soluções para o quebra-
cabeça é 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. 
 
 
Figura 1 Diagrama de estados para o quebra-cabeça. 
 
 
Pela Figura 1, fica evidente que existe um conjunto infinito de soluções, e que existem 
duas soluções de tamanho mínimo: cslcrsc e csrclsc. 
O diagrama de estados da Figura 1 tem uma característica marcante: a toda transição 
de um estado e1 para um estado e2 corresponde uma transição inversa, de e2 para e1 sob o 
mesmo símbolo. Os diagramas de estado, em geral, não precisam ter essa característica, 
como ficará evidenciado nos próximos exemplos. 
Outra característica do diagrama de estados da Figura 1, esta sim compartilhada por 
qualquer autômato finito, é que o conjunto de estados é finito. O conjunto de estados funciona, 
na realidade, como uma memória em que cada estado representa o conjunto das palavras 
que levam do estado inicial até ele. Assim, no exemplo, o estado final ∅/hlcr representa todas 
as soluções. O único mecanismo de memória possuído por esse tipo de máquina é o conjunto 
de estados. 
 
 
 
 
 
 
 
 
 
 
 
UNIVERSIDADE FEDERAL DE OURO PRETO - UFOP 
Instituto de Ciências Exatas e Aplicadas – João Monlevade 
DECSI 
 
Modelagem para certo problema matemático 
 
 Seja o problema de projetar uma máquina que, dada uma sequência de 0s e 1s, 
determine se o número representado por ela na base 2 é divisível por 6. O que se deseja é 
um projeto independente de implementação, ou seja, que capture apenas a essência de tal 
máquina, não importando se ela será mecânica, eletrônica, um programa ou o que quer que 
seja. 
 Esse problema, aparentemente tão distinto do anterior, pode ser modelado de forma 
semelhante. No exemplo anterior, uma palavra (representando uma sequência de movimentos 
de uma margem à outra) é processada da esquerda para a direita, símbolo a símbolo. Aqui, 
analogamente, a máquina deverá processar a sequência digito a dígito, da esquerda para a 
direita. Assim, deve-se considerar, após lido um prefixo x qualquer, estando o autômato em 
um determinado estado, para qual estado deve ser feita uma transição se o próximo dígito for 
0, e para qual estado deve serfeita uma transição se o próximo dígito for 1. Ora, supondo que 
η(x) seja o n´úmero representado pela palavra x, sabe-se que a palavra x0 representa o 
número 2η(x), e a palavra x1, o número 2η(x) + 1. E mais, sabe-se que, sendo η(x) mod 6 = 
r:3 
 
• 2η(x) mod 6 = 2r mod 6; 
• (2η(x) + 1) mod 6 = (2r + 1) mod 6. 
 
Com base nisso, pode-se imaginar uma máquina com seis estados, uma para cada 
resto de 0 a 5. De cada estado correspondente a resto r (0 ≤ r ≤ 5) emanam duas transições: 
Se o próximo dígito for 0, tem-se uma transição para o estado correspondente ao resto de 2r 
por 6, e se o próximo dígito for 1, tem-se uma transição para o estado correspondente ao resto 
de 2r + 1 por 6. O estado correspondente a resto 0 é estado inicial e também final. 
 
 
Figura 2 Diagrama de estados para binário módulo 6. 
 
 
Com esse mesmo diagrama de estados, modificando-se apenas o conjunto de 
estados finais, obtêm-se vários autômatos. Por exemplo, se os estados finais forem 1, 3 e 5, 
tem-se um autômato que reconhece toda palavra que representa um número cuja divisão 
por 6 tem resto ímpar. 
 
 
 
 
 
 
 
 
 
 
 
 
 
UNIVERSIDADE FEDERAL DE OURO PRETO - UFOP 
Instituto de Ciências Exatas e Aplicadas – João Monlevade 
DECSI 
 
Modelagem de um elevador 
 
 Seja um elevador destinado a servir a um prédio de três andares. O problema a ser 
abordado é o de modelar o funcionamento do elevador, o qual deverá satisfazer às 
seguintes condições: 
 
1. caso não haja chamada, o elevador fica parado onde estiver; 
2. o elevador dá prioridade ao chamado mais próximo no sentido em que estiver se 
movimentando; 
3. um chamado pode ser “desligado” manualmente. Assim, por exemplo, é possível 
existir uma chamada para um andar em certo instante e, logo em seguida, não existir mais, 
sem que o elevador se mova. 
 
Nos exemplos anteriores, a identificação dos estados e transições é bem evidente a 
partir da identificação dos aspectos importantes do problema, ou seja, a partir de sua 
modelagem. Dessa forma, inicialmente, listemos as informações relevantes do presente 
caso: 
 • os andares em que o elevador está sendo solicitado; 
 • o andar em que o elevador se encontra; 
 • o sentido em que o elevador está se movendo. 
 
 
Figura 3 Diagrama de estados para um elevador. 
 
 A partir dessas informações, o elevador pode “decidir” para qual andar ele deve se 
dirigir. Dentre elas, quais vão compor um estado e quais vão compor uma transição? 
Intuitivamente, o que faz o elevador mudar de um estado para outro é a primeira informação 
dada anteriormente, o conjunto dos andares para os quais o elevador está sendo solicitado; e 
um estado é composto das outras duas informações, já que, pela condição (3), não há 
necessidade de conferir compatibilidade de chamadas. A seguir, cada estado será 
representado por iθ, em que i refere-se ao andar em que o elevador se encontra, e θ 
corresponde a uma seta ↑, se o elevador estiver indo para cima, e ↓, se estiver indo para baixo, 
e é nulo se o andar for o primeiro (isto é, o elevador só pode se movimentar para cima) ou for 
o último andar (ou seja, o elevador só pode se movimentar para baixo). Com isso, a máquina 
para modelar o elevador que atende a três andares terá quatro estados: 1, 2 ↑, 2 ↓ e 3. Por 
esse raciocínio, para modelar um elevador para n andares, seriam necessários, obviamente, 
2+2(n−2) = 2(n−1) estados. Para cada transição, além de especificar o conjunto de chamadas 
que a ocasionou, será especificada também uma saída: a ação do elevador, representada por 
um dos três símbolos: ↑, ↓ ou ◦, conforme o elevador deva se mover para cima, para baixo, ou 
não se mover. 
Um diagrama de estados que modela o problema está mostrado na Figura 3. Observe 
que existem várias transições para o mesmo par de estados. Para simplificar a figura, em 
vez de colocar uma seta para cada uma dessas transições, optou-se por colocar todo o 
UNIVERSIDADE FEDERAL DE OURO PRETO - UFOP 
Instituto de Ciências Exatas e Aplicadas – João Monlevade 
DECSI 
 
conjunto de transições para cada par de estados como uma lista rotulando uma única seta; e 
como, nesse exemplo, a saída é a mesma para cada membro da lista, ela é especificada 
apenas uma vez, separada da lista por “/”. Além disso, um conjunto de andares é denotado 
pela sequência dos andares na ordem 1, 2, 3. Observe que: 
 
• se o conjunto de chamadas contém o andar em que está o elevador, este 
permanece no mesmo andar; apenas quando a chamada é desligada, manualmente ou não, 
o elevador pode partir para outro andar (e a máquina para outro estado); 
 • o elevador muda de sentido quando não há chamada no sentido em que está se 
movendo, caso haja chamada no outro sentido. 
 
 E interessante notar que, nesse exemplo, para qualquer palavra de entrada, tem-se 
uma palavra de saída. Não é utilizado o conceito de estado final. 
Uma configuração instantânea será uma tripla [e, x, y], em que e e x são como vistos 
na seção anterior, e y é uma palavra representando a sequência das saídas emitidas até 
aquele momento. Exemplo: 
 
 [1, 23 13 1, λ] ⊢ [2 ↑, 13 1, ↑] ⊢ [3, 1, ↑↑] ⊢ [2 ↓, λ, ↑↑↓]. 
 
 
 
 
UNIVERSIDADE FEDERAL DE OURO PRETO - UFOP 
Instituto de Ciências Exatas e Aplicadas – João Monlevade 
DECSI 
 
 
REFERÊNCIAS 
 
 
	Carlos B. Alexandre Júnior 15.2.81.24 Douglas Mendes Vieira 15.1.8286 Emily Ferreira de Brito 15.2.8030
	João Monlevade Outubro/2018
	Modelagem de um quebra-cabeça
	REFERÊNCIAS