Estou procurando bons exemplos de máquinas de estados finitos; a linguagem não é particularmente importante, apenas bons exemplos.

As implementações de código são úteis (pseudo-código generalizado), mas também são muito úteis para reunir os vários usos dos FSMs.

Os exemplos não precisam necessariamente ser baseados em computador, por exemplo, o exemplo de redes ferroviárias de Mike Dunlavey, é muito útil.

Um cofre (evento disparado)

• Estados : vários estados "bloqueados", um estado "desbloqueado"
• Transições : combinações / teclas corretas movem você dos estados bloqueados iniciais para os estados bloqueados mais perto do desbloqueado, até você finalmente desbloquear. Combinações / teclas incorretas levam você de volta ao estado bloqueado inicial (às vezes conhecido como inativo) .

Semáforo (hora acionada | sensor [evento] acionado)

• Estados : VERMELHO, AMARELO, VERDE (exemplo mais simples)
• Transições : depois de um temporizador, mude VERMELHO para VERDE, VERDE para AMARELO e AMARELO para VERMELHO. Também pode ser acionado ao detectar carros em vários estados (mais complicados).

Máquina de venda automática (evento acionado, uma variação do cofre )

• Estados : IDLE, 5_CENTS, 10_CENTS, 15_CENTS, 20_CENTS, 25_CENTS, etc, VEND, CHANGE
• Transições : Alterações de estado após a inserção de moedas, notas, transição para o VEND mediante valor correto da compra (ou mais) e, em seguida, transição para MUDAR ou OCIOSO (dependendo da ética da sua máquina de venda automática)

Exemplo de protocolo Border Gateway

O BGP é um protocolo que apóia as principais decisões de roteamento na Internet. Ele mantém uma tabela para determinar a acessibilidade dos hosts a partir de um determinado nó e tornou a Internet realmente descentralizada.

Na rede, cada nó BGP é um par e usa uma máquina de estados finitos, com um dos seis estados Inativo , Conectado , Ativo , OpenSent , OpenConfirm e Established . Cada conexão de ponto na rede mantém um desses estados.

O protocolo BGP determina as mensagens enviadas aos pares para alterar seu estado.

Statechart BPG.

Inativo

O primeiro estado inativo . Nesse estado, o BGP inicializa recursos, recusa tentativas de conexão de entrada e inicia uma conexão com o ponto.

Conectar

O segundo estado Connect . Nesse estado, o roteador aguarda a conclusão da conexão e faz a transição para o estado OpenSent, se for bem-sucedido. Se malsucedido, ele redefine o timer do ConnectRetry e transita para o estado Ativo após a expiração.

Ativo

No estado Ativo , o roteador redefine o timer do ConnectRetry para zero e retorna ao estado Connect .

OpenSent

No estado OpenSent , o roteador envia uma mensagem Open e aguarda uma em troca. As mensagens de manutenção ativa são trocadas e, após o recebimento bem-sucedido, o roteador é colocado no estado Estabelecido .

Estabelecido

No estado estabelecido , o roteador pode enviar / receber: Keepalive; Atualizar; e Mensagens de notificação de / para seus pares.

Mais informações sobre BGP estão na wikipedia

Eles são úteis para modelar todos os tipos de coisas. Por exemplo, um ciclo eleitoral pode ser modelado com os estados na linha de (governo normal) - eleição chamada -> (campanha inicial) - parlamento dissolvido -> (campanha pesada) - eleição -> (contagem de votos ) Então, (contagem de votos) - sem maioria -> (negociações da coalizão) - chegou a um acordo -> (governo normal) ou (contagem de votos) - maioria - - (governo normal). Eu implementei uma variante desse esquema em um jogo com um subgame político.

Eles também são usados ​​em outros aspectos dos jogos: a IA geralmente é baseada no estado; as transições entre menus e níveis e as transições após a morte ou o nível concluído geralmente são bem modeladas pelos FSMs.

O analisador CSV usado no plug-in jquery-csv

É um analisador gramatical básico de Chomsky Tipo III .

Um tokenizador de regex é usado para avaliar os dados char a char. Quando um caractere de controle é encontrado, o código é passado para uma instrução switch para posterior avaliação com base no estado inicial. Caracteres que não são de controle são agrupados e copiados em massa para reduzir o número de operações de cópia de seqüência necessárias.

O tokenizador:

var tokenizer = /("|,|\n|\r|[^",\r\n]+)/;

O primeiro conjunto de correspondências são os caracteres de controle: delimitador de valor (") separador de valor (,) e separador de entrada (todas as variações de nova linha). A última correspondência lida com o agrupamento de caracteres sem controle.

Existem 10 regras que o analisador deve atender:

• Regra # 1 - Uma entrada por linha, cada linha termina com uma nova linha
• Regra # 2 - Nova linha final no final do arquivo omitida
• Regra # 3 - Primeira linha contém dados do cabeçalho
• Regra # 4 - Os espaços são considerados dados e as entradas não devem conter vírgula à direita
• Regra # 5 - As linhas podem ou não ser delimitadas por aspas duplas
• Regra # 6 - Os campos contendo quebras de linha, aspas duplas e vírgulas devem ser colocados entre aspas duplas
• Regra nº 7 - Se aspas duplas forem usadas para colocar campos, uma aspas dupla aparecendo dentro de um campo deve ser escapada precedendo-a com outra aspas
• Alteração 1 - Um campo não citado pode ou pode
• Alteração 2 - Um campo citado pode ou não
• Alteração 3 - O último campo de uma entrada pode ou não conter um valor nulo

Nota: As 7 principais regras são derivadas diretamente do IETF RFC 4180 . Os três últimos foram adicionados para cobrir casos avançados introduzidos por aplicativos modernos de planilhas (ex Excel, Google Spreadsheet) que não delimitam (ou seja, citam) todos os valores por padrão. Tentei contribuir com as alterações na RFC, mas ainda não recebi uma resposta à minha pergunta.

Chega de conclusão, aqui está o diagrama:

Estados:

1. estado inicial de uma entrada e / ou um valor
2. uma cotação de abertura foi encontrada
3. uma segunda cotação foi encontrada
4. um valor não cotado foi encontrado

Transições:

• uma. verifica os valores entre aspas (1), valores não citados (3), valores nulos (0), entradas nulas (0) e novas entradas (0)
• b. verifica se há um segundo caractere de cotação (2)
• c. verifica se há uma cotação de escape (1), final do valor (0) e final da entrada (0)
• d. verifica o final do valor (0) e o final da entrada (0)

Nota: Na verdade, está faltando um estado. Deve haver uma linha de 'c' -> 'b' marcada com o estado '1' porque um segundo delimitador com escape significa que o primeiro delimitador ainda está aberto. De fato, provavelmente seria melhor representá-lo como outra transição. Criando isso é uma arte, não existe uma maneira correta.

Nota: Também está faltando um estado de saída, mas em dados válidos o analisador sempre termina na transição 'a' e nenhum dos estados é possível porque não há mais nada a analisar.

A diferença entre estados e transições:

Um estado é finito, o que significa que só pode ser inferido como significando uma coisa.

Uma transição representa o fluxo entre estados, portanto pode significar muitas coisas.

Basicamente, o relacionamento estado-> transição é 1 -> * (isto é, um para muitos). O estado define 'o que é' e a transição define 'como é tratado'.

Nota: Não se preocupe se a aplicação de estados / transições não parecer intuitiva, não é intuitiva. Foi preciso uma correspondência extensa com alguém muito mais esperto do que eu antes de finalmente entender o conceito.

O pseudo-código:

csv = // csv input string

// init all state & data
state = 0
value = ""
entry = []
output = []

endOfValue() {
  entry.push(value)
  value = ""
}

endOfEntry() {
  endOfValue()
  output.push(entry)
  entry = []
}

tokenizer = /("|,|\n|\r|[^",\r\n]+)/gm

// using the match extension of string.replace. string.exec can also be used in a similar manner
csv.replace(tokenizer, function (match) {
  switch(state) {
    case 0:
      if(opening delimiter)
        state = 1
        break
      if(new-line)
        endOfEntry()
        state = 0
        break
      if(un-delimited data)
        value += match
        state = 3
        break
    case 1:
      if(second delimiter encountered)
        state = 2
        break
      if(non-control char data)
        value += match
        state = 1
        break
    case 2:
      if(escaped delimiter)
        state = 1
        break
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
    case 3:
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
  }
}

Nota: Esta é a essência, na prática, há muito mais a considerar. Por exemplo, verificação de erros, valores nulos, uma linha em branco à direita (ou seja, qual é válida), etc.

Nesse caso, o estado é a condição das coisas quando o bloco de correspondência de expressão regular termina uma iteração. A transição é representada como as instruções de caso.

Como seres humanos, temos a tendência de simplificar operações de baixo nível em resumos de nível superior, mas trabalhar com um FSM está trabalhando com operações de baixo nível. Embora seja muito fácil trabalhar com estados e transições individualmente, é inerentemente difícil visualizar o todo de uma só vez. Achei mais fácil seguir os caminhos individuais de execução repetidamente, até que eu pudesse intuir como as transições acontecem. É como aprender matemática básica, você não será capaz de avaliar o código de um nível superior até que os detalhes de baixo nível se tornem automáticos.

Além: Se você observar a implementação real, há muitos detalhes ausentes. Primeiro, todos os caminhos impossíveis lançam exceções específicas. Deveria ser impossível atingi-los, mas se algo quebrar, eles absolutamente acionarão exceções no corredor de teste. Segundo, as regras do analisador para o que é permitido em uma sequência de dados CSV 'legal' são bastante soltas, portanto o código necessário para lidar com muitos casos específicos de borda. Independentemente disso, esse foi o processo usado para zombar do FSM antes de todas as correções, extensões e ajustes finos.

Como na maioria dos projetos, não é uma representação exata da implementação, mas descreve as partes importantes. Na prática, existem três funções diferentes do analisador derivadas desse design: um divisor de linha específico para csv, um analisador de linha única e um analisador de várias linhas completo. Todos eles operam de maneira semelhante, diferem na maneira como lidam com os caracteres de nova linha.

FSM simples em Java

int i=0;

while (i<5) {
 switch(i) {
   case 0:
     System.out.println("State 0");
     i=1;
     break;
   case 1:
     System.out.println("State 1");
     i=6;
     break;
   default:
     System.out.println("Error - should not get here");
     break;      
  }

} 

Ai está. OK, não é brilhante, mas mostra a ideia.

Você encontrará frequentemente FSMs em produtos de telecomunicações porque eles oferecem uma solução simples para uma situação complexa.

Descobri que pensar em / modelar um elevador (elevador) é um bom exemplo de uma máquina de estados finitos. Requer pouco na introdução, mas fornece uma situação longe de trivial para implementar.

Os estados estão, por exemplo, no térreo, no primeiro andar, etc, e movendo o terreno para o primeiro andar ou movendo-se do terceiro para o térreo, mas atualmente entre os andares 3 e 2, e assim por diante.

O efeito dos botões na gaiola de elevação e nos próprios pisos fornece entradas, cujo efeito depende do botão pressionado junto com o estado atual.

Cada andar, exceto a parte superior e inferior, terá dois botões: um para solicitar que o elevador suba e o outro que desça.

OK, aqui está um exemplo. Suponha que você queira analisar um número inteiro. Seria algo como dd*onde destá um dígito inteiro.

state0:
    if (!isdigit(*p)) goto error;
    p++;
    goto state1;
state1:
    if (!isdigit(*p)) goto success;
    p++;
    goto state1;

Obviamente, como @Gary disse, você pode disfarçar esses gotos por meio de uma instrução switch e variável de estado. Observe que pode ser estruturado para este código, que é isomórfico para a expressão regular original:

if (isdigit(*p)){
    p++;
    while(isdigit(*p)){
        p++;
    }
    // success
}
else {
    // error
}

Claro que você também pode fazê-lo com uma tabela de pesquisa.

Máquinas de estados finitos podem ser criadas de várias maneiras, e muitas coisas podem ser descritas como instâncias de máquinas de estados finitos. Não é uma "coisa", mas um conceito, para pensar sobre as coisas.

Exemplo de Rede Ferroviária

Um exemplo de FSM é uma rede ferroviária.

Há um número finito de interruptores em que um trem pode entrar em uma das duas faixas.

Há um número finito de faixas conectando esses switches.

A qualquer momento, um trem está em uma linha, pode ser enviado para outra linha cruzando um comutador, com base em um único bit de informação de entrada.

Máquina de estados finitos em Ruby:

module Dec_Acts
 def do_next
    @now = @next
    case @now
    when :invite
      choose_round_partner
      @next = :wait
    when :listen
      @next = :respond
    when :respond
      evaluate_invites
      @next = :update_in
    when :wait
      @next = :update_out
    when :update_in, :update_out
      update_edges
      clear_invites
      @next = :exchange
    when :exchange
      update_colors
      clear_invites
      @next = :choose
    when :choose
      reset_variables
      choose_role
    when :done
      @next = :done
    end
  end
end

Esse é o comportamento de um único nó de computação em um sistema distribuído, configurando um esquema de comunicação baseado em link. Mais ou menos. Na forma gráfica, é algo parecido com isto:

Confira este link para alguns exemplos simples de análise lexical (FSM):

http://ironbark.bendigo.latrobe.edu.au/subjects/SS/clect/clect03.html

Você também pode conferir o "livro do dragão" para exemplos (não é leitura leve)

http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools

Na prática, as Máquinas de Estado são frequentemente usadas para:

• Finalidades de design (modelando as diferentes ações em um programa)
• Analisadores de linguagem natural (gramática)
• Análise de String

Um exemplo seria uma Máquina de Estado que varre uma string para ver se ela possui a sintaxe correta. Os códigos postais holandeses, por exemplo, estão formatados como "1234 AB". A primeira parte pode conter apenas números, a segunda apenas letras. Uma máquina de estado pode ser escrita para acompanhar se está no estado NUMBER ou no estado LETTER e, se encontrar entrada incorreta, rejeite-a.

Essa máquina de estados aceitadores possui dois estados: numérico e alfa. A máquina de estados inicia no estado numérico e começa a ler os caracteres da sequência a ser verificada. Se caracteres inválidos forem encontrados durante qualquer um dos estados, a função retornará com um valor False, rejeitando a entrada como inválida.

Código Python:

import string

STATE_NUMERIC = 1
STATE_ALPHA = 2

CHAR_SPACE = " "

def validate_zipcode(s):
cur_state = STATE_NUMERIC

for char in s:
    if cur_state == STATE_NUMERIC:
        if char == CHAR_SPACE:
            cur_state = STATE_ALPHA
        elif char not in string.digits:
            return False
    elif cur_state == STATE_ALPHA:
        if char not in string.letters:
            return False
return True

zipcodes = [
    "3900 AB",
    "45D6 9A",
]

for zipcode in zipcodes:
    print zipcode, validate_zipcode(zipcode)

Fonte: Máquinas de Estados (Finitos) na prática