Máquina de estados

Uma máquina de estados consiste num modelo de computação composto por um conjunto finito de estados, transições entre estados e acções efectuadas no decurso do processo. Cada um dos estados de uma máquina de estados descreve o modo em que a máquina se encontra. O estado da máquina pode ser alterado aquando da ocorrência de um evento ou da leitura de um símbolo a partir de um dispositivo de entrada.

A transição entre estados depende unicamente do estado em que a máquina se encontra e do símbolo que é lido. A máquina cessa o funcionamento quando é atingido algum dos estados finais.

No decurso do funcionamento de uma máquina de estados, podem ser tomadas determinadas acções:

 

  • Acção de entrada: é tomada sempre que a máquina entra num determinado estado
  • Acção de transição: é tomada sempre que a máquina transita entre dois estados
  • Acção de saída: é tomada sempre que a máquina abandona um determinado estado

Uma máquina de estados pode ser representada um diagrama do tipo apresentado na figura.

mef_integer_float

No esquema anterior está representada uma máquina de estados simples. A mesma máquina pode ser representada pela tabela:

 

 

entrada

algarismo

ponto

s_algarismo

algarismo

algarismo

algarismo

s_ponto

ponto

ponto

erro

símbolo de saída

erro

sucesso

erro

Cada entrada da tabela indica o estado para o qual ocorre a transição sempre que se encontra o símbolo indicado nessa linha e a máquina se encontra no estado especificado na coluna. Desta forma, supondo que a máquina se encontra no estado algarismo e encontra o símbolo s_ponto, esta irá transitar para o estado ponto.

Observando com atenção a máquina de estados representada, divisam-se imediatamente três conjuntos distintos:

 

  • Conjunto de estados – ST={entrada,algarismo, ponto, erro, sucesso}
  • Conjunto de símbolos – SYMB={s_algarismo, s_ponto, símbolo de saída}
  • Conjunto de estados terminais – F={sucesso, erro}

A tabela representa uma função

mef_funcaco

designada por função de transição.

A função de transição associa ao estado actual da máquina e ao símbolo lido o estado para o qual esta vai transitar. Desta forma, pode-se definir formalmente a máquina de estados como sendo uma quíntupla (SYMB,ST,s,f,F), onde

  • SYMB corresponde ao alfabeto, isto é, é um conjunto de símbolos
  • ST é um conjunto de estados
  • s representa o estado inicial
  • f representa a função de transição
  • F é um conjunto de estados finais

A máquina de estados pára sempre que é atingido um determinado estado final. A cada entrada da tabela podem-se associar acções para a respectiva transição. Aos estados também podem ser agregadas acções de entrada e de saída. No caso da representação esquemática, as acções de entrada e saída são representadas nos vértices do grafo e as acções de transição são representadas nas arestas.

As máquinas de estados podem ser aplicadas numa diversidade de problemas de ciência de computadores. A máquina de estados supracitada pode ser utilizada para determinar se um determinado conjunto de caracteres pode ou não representar um número inteiro ou decimal sem ter em consideração a notação exponencial, a quantidade de casas decimais que podem ser lidas ou o sinal do número.

Supondo que a máquina lê os símbolos da cadeia “12.34”. Começa no estado entrada e lê o símbolo 1 que é um algarismo, transitando para o estado algarismo. Depois lê o símbolo 2 que faz com que a máquina se mantenha no mesmo estado. Quando é obtido o símbolo s_ponto, a máquina transita para o estado ponto transitando para o estado algarismo quando são lidos sequencialmente os símbolos 3 e 4. Quando encontra o final da cadeia (símbolo de saída) a máquina transita para o estado sucesso. Se a sequência de símbolos introduzida for “1.”, a máquina transita para o estado algarismo depois de ler o símbolo 1 e passa ao estado ponto depois de ler o símbolo s_ponto. Uma vez que o próximo símbolo corresponde ao símbolo de saída, a máquina transita para o estado erro que corresponde a um estado final.

Para o caso da máquina identificar completamente números decimais incluindo a notação científica bem como o reconhecimento do sinal, será necessária a introdução de novos símbolos bem como de novos estados. No esquema seguinte, pode-se visualizar os símbolos e estados adendados à máquina anterior por forma a que esta possa reconhecer números decimais de uma forma geral.

mef_integer_float_complete

A nova máquina pode ser representada pela tabela que se segue.

 

entrada

algar

ponto

expnl

menos

exp

negat

s_algarismo

algar

algar

algar

exp

algar

exp

exp

s_ponto

ponto

ponto

erro

erro

ponto

erro

erro

s_menos

menos

erro

erro

negat

erro

erro

erro

s_E | s_e

erro

expnl

erro

erro

erro

erro

erro

s_saída

erro

sucesso

erro

erro

erro

sucesso

erro

Repare-se que a máquina de estados não guarda memória dos estados pelos quais passou. Assim sendo, não é possível utilizar a técnica para verificar se uma expressão que inclua parêntesis está bem construída. No entanto, uma vez que se podem associar acções aos estados e respectivas transições, é possível adornar a máquina com a capacidade de memorizar estados em que já esteve.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Computadores e Internet. ligação permanente.

Uma resposta a Máquina de estados

  1. Filipe diz:

    passei por aqui e vi que tens um blog mt fixe, é pena eu não ter mais assunto mas que se lixe……hehehehe tb sou poeta heheh:)

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s