Máquinas de Estado ou Automata

1. INTRODUÇÃO

Máquinas de Estado ou Autômato é um modelo matemático capaz de modelar diversas situações do mundo real ou não, para uma linguagem de formalismos e capaz de ser computada. Neste trabalho será usado um Autômato Finito NãoDeterminístico para a modelagem de um problema (Going Together, fonte URI), no qual a partir do processamento das palavras o estado final indicará a chegada de todos os personagens na célula alvo.

 

2. OBJETIVO

A modelagem do Jogo Going Together compete à representação das células em que os personagens (robôs) podem estar ao longo do jogo. Sendo essas células obstáculos, células vazias ou células alvo.

Ao final do processamento do autômato com uma palavra que seja aceita pelo mesmo, o resultado será o final do jogo onde os três personagens devem estar em células alvo.

 

3. DESCRIÇÃO DO PROBLEMA

Chegando junto trata-se de um jogo que se passa em um cenário de labirinto, cujo objetivo é fazer com que todos os personagens (Aneed, Ben, Cindy) cheguem às células alvo, o que significaria que eles conseguiram escapar.

No labirinto existem três tipos de células, as células vazias, que indicam que o robô esta livre para passar por ela, as células com obstáculos, que não permitem o avanço, portanto o robô mantém sua posição na célula anterior e por fim as células alvo, que indicam a chegada do robô ao seu objetivo.

Os robôs podem se movimentar para a célula do norte, sul, leste e oeste, isto é, se nenhuma delas for uma célula obstáculo.

4. MODELAGEM

De acordo com a descrição do problema (Item 3) os personagens começam em células vazias, e tem fim quando a partir de um determinado número de movimentos (lembrando que o movimento é executado por todos os personagens ao mesmo tempo) os três personagens chegam a células alvo.

A modelagem resultou num Autômato Finito Não Determinístico (AFND).

4.1. ALFABETO

O Alfabeto desse autômato será composto por apenas uma palavra (m), palavra esta que representara o movimento, seja esse para o Norte, Sul, Leste e Oeste. Dessa forma o alfabeto do autômato é definido abaixo:

 = {m}

4.2. ESTADOS

O problema em sua forma original encontra-se disponível no URI Online Judge, o link para acessá-lo se encontra nas referências bibliográficas. Entretanto abaixo descrevemos o problema de forma mais simplificada para melhor compreensão.

Os estados do autômato serão as possíveis combinações de células em que os três personagens se encontram. O nome do estado é composto por 3 (três) letras onde a primeira representa qual o tipo de célula em que o primeiro personagem está, a segunda letra representará qual o tipo de célula em que o segundo personagem está e assim sucessivamente.

Pela descrição do problema (Item 3) define-se que somente existem 3 (três) tipos de células, Células Vazias, Células Alvo e Obstáculos. Estes tipos de células são representados pelas letras “V”, ”F”, ”O” respectivamente. Assim, se os 3 (três) personagens estiverem respectivamente em uma Célula Vazia, Célula Vazia e Obstáculo o nome do estado referente é “VVO”.

O estado inicial é o estado onde os 3 (três) personagens estão em Células Vazias, assim o estado inicial do autômato é “VVV”.

Dessa forma o conjunto dos estados do autômato é:

Q = {VVV, VVF, VVO, VFV, VFF, VFO, VOV, VOF, VOO, FVV, FVF, FVO, FFV, FFF, FFO, FOV, FOF, FOO, OVV, OVF, OVO, OFV, OFF, OFO, OOV, OOF, OOO}

O conjunto de estados iniciais é:

q0 = {VVV}

O conjunto de estados final é:

F = {FFF}

4.3. FUNÇÃO PROGRAMA

A função programa do autômato é definida pela tabela a seguir:

d m Ԑ

VVV {VDF, FOO, FVV, FOF, OVV, FVF, VOV, VOO, VFF, FFV, FFF, OVO, OFO,

VVO,VVF, FOV, OFV, OOV, OOF, OFF, OOO, FVO, OVF, FVF, FFO, VVV} Ø

VVF {VFF, VOF, FOF, FFF, FVF, OFF, OOF,OVF} Ø

VVO Ø {VVV}

VFV {VFO,VFF,OFV,OFO,OFF,FFF,FFO,FFV} Ø

VFF {FFF,OFF} Ø

VFO Ø {VFV}

VOV Ø {VVV}

VOF Ø {VVF}

VOO Ø {VVV}

FVV {FFF,FOV, FOF,FFV,FVF,FFO,FFF} Ø