usos para as máquinas de estado [fechado]
https://stackoverflow.com/questions/255797
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Em que áreas da programação que eu iria usar máquinas de estado? Por quê ? Como eu poderia implementar um?
EDIT:. forneça um exemplo prático, se não é pedir demais
Solução
Em que áreas da programação que eu iria usar uma máquina de estado?
Use uma máquina de estado para representar um objeto (real ou lógica) que podem existir em um número limitado de condições ( " estados ") e progride de um estado para o outro de acordo com um conjunto fixo de regras.
Por que eu iria usar uma máquina de estado?
A máquina de estado é muitas vezes um muito forma compacta para representar um conjunto de regras e condições complexas, e para processar várias entradas. Você verá máquinas de estado em dispositivos embarcados que têm memória limitada. bem implementada, uma máquina de estado está autodocumentados porque cada estado lógico representa uma condição física. Uma máquina de estado pode ser incorporado em um pequena quantidade de código em comparação com seu equivalente processual e corre de forma extremamente eficiente. Além disso, as regras que governam as mudanças de estado muitas vezes podem ser armazenados como dados em uma tabela, fornecendo uma representação compacta que pode ser facilmente mantida.
Como posso implementar um?
Trivial exemplo:
enum states { // Define the states in the state machine.
NO_PIZZA, // Exit state machine.
COUNT_PEOPLE, // Ask user for # of people.
COUNT_SLICES, // Ask user for # slices.
SERVE_PIZZA, // Validate and serve.
EAT_PIZZA // Task is complete.
} STATE;
STATE state = COUNT_PEOPLE;
int nPeople, nSlices, nSlicesPerPerson;
// Serve slices of pizza to people, so that each person gets
/// the same number of slices.
while (state != NO_PIZZA) {
switch (state) {
case COUNT_PEOPLE:
if (promptForPeople(&nPeople)) // If input is valid..
state = COUNT_SLICES; // .. go to next state..
break; // .. else remain in this state.
case COUNT_SLICES:
if (promptForSlices(&nSlices))
state = SERVE_PIZZA;
break;
case SERVE_PIZZA:
if (nSlices % nPeople != 0) // Can't divide the pizza evenly.
{
getMorePizzaOrFriends(); // Do something about it.
state = COUNT_PEOPLE; // Start over.
}
else
{
nSlicesPerPerson = nSlices/nPeople;
state = EAT_PIZZA;
}
break;
case EAT_PIZZA:
// etc...
state = NO_PIZZA; // Exit the state machine.
break;
} // switch
} // while
Notas:
-
O exemplo usa um
switch()com estadoscase/breakexplícitas para a simplicidade. Na prática, umcase, muitas vezes, "cair" para o próximo estado. -
Para facilitar a manutenção de uma grande máquina de estado, o trabalho realizado em cada
casepode ser encapsulado em uma função de "trabalhador". Obter qualquer entrada no topo dawhile(), passá-lo para a função de trabalhador, e verificar o valor de retorno do trabalhador para calcular o próximo estado. -
Por compacidade, toda a
switch()pode ser substituída por uma matriz de ponteiros de função. Cada estado é personificada por uma função cujo valor de retorno é um ponteiro para o próximo estado. Aviso: Isto pode simplificar a máquina de estado ou torná-lo totalmente insustentável, por isso considero a implementação cuidadosamente -
Um dispositivo incorporado pode ser implementada como uma máquina de estados que sai apenas em um erro catastrófico, após o qual ele executa um hard reset e re-entra na máquina de estado.
Outras dicas
Alguns grandes respostas já. Para uma perspectiva ligeiramente diferente, considere procurar um texto em uma seqüência maior. Alguém já mencionou expressões regulares e isso é realmente apenas um caso especial, embora importante.
Considere a seguinte chamada de método:
very_long_text = "Bereshit bara Elohim et hashamayim ve'et ha'arets." …
word = "Elohim"
position = find_in_string(very_long_text, word)
Como você poderia implementar find_in_string? A abordagem mais fácil seria usar um loop aninhado, algo como isto:
for i in 0 … length(very_long_text) - length(word):
found = true
for j in 0 … length(word):
if (very_long_text[i] != word[j]):
found = false
break
if found: return i
return -1
Além do fato de que este é ineficiente, forma uma máquina de estado ! Os estados aqui são um pouco escondido; deixe-me reescrever o código ligeiramente para torná-los mais visíveis:
state = 0
for i in 0 … length(very_long_text) - length(word):
if very_long_text[i] == word[state]:
state += 1
if state == length(word) + 1: return i
else:
state = 0
return -1
Os diferentes estados aqui representam diretamente todos diferentes posições na palavra que procurar. Existem duas transições para cada nó no gráfico: se as letras corresponder, vá para o próximo estado; para cada outra entrada (ou seja, todas as outras letras na posição atual), voltar a zero.
Esta ligeira reformulação tem uma enorme vantagem: agora pode ser ajustado para produzir um melhor desempenho utilizando algumas técnicas básicas. Na verdade, cada algoritmo avançado seqüência de busca (descontando estruturas de dados de índice para o momento) constrói no topo desta máquina de estado e melhora alguns aspectos do mesmo.
Que tipo de tarefa?
Qualquer tarefa, mas pelo que tenho visto, de análise de qualquer tipo é frequentemente implementada como uma máquina de estado.
Por quê?
A análise de uma gramática geral, não é uma tarefa simples. Durante a fase de projeto é bastante comum que um diagrama de estado é desenhado para testar o algoritmo de análise. Traduzindo isso para uma implementação de máquina de estado é uma tarefa bastante simples.
Como?
Bem, você está limitado apenas pela sua imaginação.
Eu já vi isso feito com caso declarações e loops .
Eu já vi isso feito com rótulos e Goto declarações
Eu mesmo vi isso feito com estruturas de ponteiros de função que representam o estado atual. Quando o estado muda, um ou mais função de ponteiro é atualizado.
Eu já vi isso feito em código só, onde uma mudança de estado simplesmente significa que você está executando em uma seção diferente do código. (Sem variáveis ??de estado, e código redundent quando necessário. Isso pode ser demonstrado como uma maneira muito simples tipo, que é útil apenas para muito pequenos conjuntos de dados.
int a[10] = {some unsorted integers};
not_sorted_state:;
z = -1;
while (z < (sizeof(a) / sizeof(a[0]) - 1)
{
z = z + 1
if (a[z] > a[z + 1])
{
// ASSERT The array is not in order
swap(a[z], a[z + 1]; // make the array more sorted
goto not_sorted_state; // change state to sort the array
}
}
// ASSERT the array is in order
Não há variáveis ??de estado, mas o próprio código representa o estado
O Estado padrão de design é uma maneira orientada a objeto para representar o estado de um objeto meio de uma máquina de estado finito. Ele geralmente ajuda a reduzir a complexidade lógica de implementação desse objeto (aninhados se de, muitas bandeiras, etc.)
A maioria dos fluxos de trabalho pode ser implementado como máquinas de estado. Por exemplo, o tratamento dos pedidos de licença ou ordens.
Se você estiver usando .NET, tente o Windows Workflow Foundation. Você pode implementar uma máquina de estado de fluxo de trabalho muito rapidamente com ele.
Se você estiver usando C #, a qualquer hora você escreve um bloco iterador você está pedindo o compilador para construir uma máquina de estado para você (mantendo o controle de onde você está no iterador etc).
Aqui está um exemplo testado e funcionando de uma máquina de estado. Digamos que você está em um córrego de série (porta serial, TCP / IP dados ou arquivo são exemplos típicos). Neste caso, eu estou procurando uma estrutura de pacote específico que pode ser dividido em três partes, sincronização, comprimento e carga útil. Eu tenho três estados, é ocioso, esperando a sincronização, o segundo é que temos uma boa sincronia o próximo byte deve ser de comprimento, eo terceiro estado é acumular a carga útil.
O exemplo é puramente de série com apenas um tampão, como está escrito aqui ele vai se recuperar de uma má byte ou pacote, possivelmente descartar um pacote, mas, eventualmente, recuperar, você pode fazer outras coisas como uma janela deslizante para permitir a recuperação imediata. Este seria o lugar onde você tem dizer um pacote parcial que é cortada, em seguida, inicia uma nova pacote completo, o código abaixo não vai detectar isso e vai jogar fora a parcial, bem como o pacote inteiro e recuperar no próximo. A janela deslizante iria salvá-lo lá, se você realmente necessário para processar todas as integrais dos pacotes.
Eu uso este tipo de uma máquina de estado o tempo todo seja fluxos de dados seriais, TCP / IP, arquivo i / o. Ou talvez protocolos TCP / IP-se, digamos que você deseja enviar um e-mail, abra a porta, espera para o servidor para enviar uma resposta, enviar HELO, espera para o servidor para enviar um pacote, enviar um pacote, espera pela resposta, etc. Essencialmente, nesse caso, bem como no caso abaixo você pode estar em marcha lenta à espera de que o próximo byte / pacote para entrar. para lembrar o que você estava esperando, também para re-utilizar o código que espera por algo que você pode usar variáveis ??de Estado. Da mesma forma que máquinas de estado são usadas na lógica (esperando o próximo relógio, o que eu estava esperando).
Assim como em lógica, você pode querer fazer algo diferente para cada estado, neste caso, se eu tiver um bom padrão de sincronização eu redefinir o deslocamento em meu armazenamento, bem como repor o acumulador soma de verificação. O estado tamanho do pacote demonstra um caso em que você pode querer abortar fora do caminho de controle normal. Nem todos, na verdade, muitas máquinas de estado pode pular ou loop de maio em torno de dentro do caminho normal, o que está abaixo é praticamente linear.
Espero que este seja útil e desejo que as máquinas estatais foram utilizados mais em software.
Os dados de teste tem problemas intencionais com que a máquina do estado recupera de. Há alguns dados de lixo após o primeiro pacote bom, um pacote com uma má checksum, e um pacote com um comprimento inválido. Minha saída foi:
bom pacote: FA0712345678EB sincronização inválido padrão 0x12 sincronização inválido padrão 0x34 sincronização inválido padrão 0x56 Soma de verificação de erro 0xBF comprimento de pacote inválido 0 sincronização inválido padrão 0x12 sincronização inválido padrão 0x34 sincronização inválido padrão 0x56 sincronização inválido padrão 0x78 sincronização inválido padrão 0xEB bom pacote: FA081234567800EA não mais dados de teste
Os dois bons pacotes no fluxo foram extraídos apesar dos dados errados. E os dados ruins foi detectada e tratada.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
unsigned char testdata[] =
{
0xFA,0x07,0x12,0x34,0x56,0x78,0xEB,
0x12,0x34,0x56,
0xFA,0x07,0x12,0x34,0x56,0x78,0xAA,
0xFA,0x00,0x12,0x34,0x56,0x78,0xEB,
0xFA,0x08,0x12,0x34,0x56,0x78,0x00,0xEA
};
unsigned int testoff=0;
//packet structure
// [0] packet header 0xFA
// [1] bytes in packet (n)
// [2] payload
// ... payload
// [n-1] checksum
//
unsigned int state;
unsigned int packlen;
unsigned int packoff;
unsigned char packet[256];
unsigned int checksum;
int process_packet( unsigned char *data, unsigned int len )
{
unsigned int ra;
printf("good packet:");
for(ra=0;ra<len;ra++) printf("%02X",data[ra]);
printf("\n");
}
int getbyte ( unsigned char *d )
{
//check peripheral for a new byte
//or serialize a packet or file
if(testoff<sizeof(testdata))
{
*d=testdata[testoff++];
return(1);
}
else
{
printf("no more test data\n");
exit(0);
}
return(0);
}
int main ( void )
{
unsigned char b;
state=0; //idle
while(1)
{
if(getbyte(&b))
{
switch(state)
{
case 0: //idle
if(b!=0xFA)
{
printf("Invalid sync pattern 0x%02X\n",b);
break;
}
packoff=0;
checksum=b;
packet[packoff++]=b;
state++;
break;
case 1: //packet length
checksum+=b;
packet[packoff++]=b;
packlen=b;
if(packlen<3)
{
printf("Invalid packet length %u\n",packlen);
state=0;
break;
}
state++;
break;
case 2: //payload
checksum+=b;
packet[packoff++]=b;
if(packoff>=packlen)
{
state=0;
checksum=checksum&0xFF;
if(checksum)
{
printf("Checksum error 0x%02X\n",checksum);
}
else
{
process_packet(packet,packlen);
}
}
break;
}
}
//do other stuff, handle other devices/interfaces
}
}
As máquinas de estado estão em toda parte. máquinas de estado são fundamentais para interfaces de comunicação em que uma mensagem precisa ser analisado como ele é recebido. Além disso, tem havido muitas vezes no desenvolvimento de sistemas embarcados que eu precisava separar uma tarefa em várias tarefas por causa de rigorosas restrições de tempo.
infra-estrutura de QA, destina-se a tela-raspagem ou de outro modo executado por meio de um processo em teste. (Esta é a minha área particular de experiência; eu construí uma estrutura de máquina de estado em Python para o meu último empregador com suporte para empurrar o estado atual em uma pilha e usando vários métodos de selecção manipulador de estado para uso em todas as nossas screen scrapers baseada TTY) . Os ataques modelo conceitual bem, como correr através de uma aplicação TTY, ele passa por um número limitado de estados conhecidos, e pode ser movida de volta para os antigos (pensar em usar um menu aninhado). Este foi liberado (com permissão disse do empregador); usar Bazaar para verificar http://web.dyfis.net/bzr/isg_state_machine_framework/ se você quiser ver o código.
ticket,-gestão de processos e fluxo de trabalho de sistemas - se o seu bilhete tem um conjunto de regras que determinam o seu movimento entre NOVO, triagem, em andamento, as necessidades de QA, FALHOU-QA e verificada (por exemplo), você' tenho uma máquina de estado simples.
Edifício pequeno, sistemas embarcados facilmente demonstráveis ??- sinalização luminosa de tráfego é um exemplo-chave, onde a lista de todos os estados possíveis tem para ser totalmente enumeradas e conhecido
.Analisadores e lexers são fortemente baseado no estado-máquina, porque a forma como algo em streaming é determinado é baseado em onde você está no momento.
Um monte de design de hardware digital envolve a criação de máquinas de estado para especificar o comportamento de seus circuitos. Ele vem até um pouco se você estiver escrevendo VHDL.
A FSM é usado em todos os lugares você tiver vários estados e necessidade de transição para um estado diferente de estímulo.
(Acontece que este abrange a maioria dos problemas, pelo menos teoricamente)
expressões regulares são outro exemplo de onde as máquinas de estados finitos (ou "autômatos de estados finitos" ) entre no jogo.
A expressão regular compilada é uma máquina de estado finito e os conjuntos de cordas que as expressões regulares podem combinar são exatamente os idiomas que finito autômatos estado pode aceitar (chamados de "linguagens regulares").
Eu não vi nada aqui que realmente explicou a razão de eu vê-los usado.
Para fins práticos, um programador normalmente tem de adicionar um quando ele é forçado a retornar uma thread / saída à direita no meio de uma operação.
Por exemplo, se você tiver um pedido HTTP multi-estado, você pode ter código do servidor que se parece com isso:
Show form 1
process form 1
show form 2
process form 2
A coisa é, cada vez que você mostrar um formulário, você tem que sair fora de toda a sua discussão no servidor (na maioria dos idiomas), mesmo se o seu código de todos os fluxos juntos logicamente e usa as mesmas variáveis.
O ato de colocar uma pausa no código e retornar o fio é normalmente feito com uma instrução switch e cria o que é chamado uma máquina de estado (Very versão Basic).
Como você se tornam mais complexas, ele pode ficar muito difícil descobrir o que os estados são válidos. As pessoas costumam seguida, definir um " Transição Estado Tabela " para descrever todas as transições de estado.
Eu escrevi um Biblioteca Estadual de máquina , o conceito principal é que você pode realmente implementar sua tabela de transição de estado diretamente. Foi um exercício muito legal, não tenho certeza o quão bem ele vai passar por cima embora ...
máquinas de estados finitos pode ser usado para análise morfológica em qualquer linguagem natural.
Teoricamente, isso significa que a morfologia ea sintaxe são divididos entre os níveis computacionais, um ser no máximo de estados finitos, e o outro ser, no máximo contexto levemente sensíveis (portanto, a necessidade de outros modelos teóricos para a conta por palavra-to- palavra em vez de relacionamentos morfema-a-morfema).
Isto pode ser útil na área de tradução automática e palavra lustro. Ostensivamente, eles são de baixo custo apresenta para extrair para aplicações de aprendizado de máquina menos triviais em PNL, tais como análise sintáctica ou dependência.
Se você estiver interessado em aprender mais, você pode conferir Finite State Morfologia por Beesley e Karttunen, ea Xerox Finite State Toolkit eles projetaram no PARC.
Eu tenho um exemplo de um sistema atual que estou trabalhando. Eu estou no processo de construção de um sistema de negociação de ações. O processo de acompanhamento do estado de uma ordem pode ser complexo, mas se você construir um diagrama de estado para o ciclo de vida de uma ordem que faz aplicação de novas transações de entrada para a ordem existente muito mais simples. Há muitos menos comparações necessárias na aplicação dessa transação se você sabe de seu estado atual que a nova transação só pode ser uma de três coisas ao invés de uma das 20 coisas. Isso torna o código muito mais eficiente.
código de Estado conduzido é uma boa maneira de implementar certos tipos de lógica (analisadores sendo um exemplo). Isso pode ser feito de várias maneiras, por exemplo:
-
condução Estado que pouco de código que realmente está sendo executado em um determinado ponto (ou seja, o estado está implícito no pedaço de código que você está escrevendo). recursiva descida analisadores são um bom exemplo deste tipo de código.
-
Estado condução o que fazer em uma condicional, como um switch.
-
máquinas de estado explícitas, tais como os gerados por ferramentas geradoras analisador tal como Lex e Yacc .
Nem todos os códigos impulsionado estado é utilizado para a análise. Um gerador de máquina de estado geral é smc . Ele inala uma definição de uma máquina de estado (na língua) e ele vai cuspir código para a máquina de estado em uma variedade de idiomas.
Boas respostas. Aqui está o meu 2 centavos. Máquinas de Estados Finitos são uma ideia teórica que pode ser implementado várias maneiras diferentes, como uma mesa, ou como um interruptor de tempo (mas não diga a ninguém que é uma maneira de dizer Goto horrores ). É um teorema que nenhum corresponde FSM para uma expressão regular, e vice-versa. Desde um regular corresponde expressão a um programa estruturado, você pode por vezes apenas escrever um programa estruturado para implementar o seu FSM. Por exemplo, um simples analisador de números poderia ser escrito ao longo das linhas de:
/* implement dd*[.d*] */
if (isdigit(*p)){
while(isdigit(*p)) p++;
if (*p=='.'){
p++;
while(isdigit(*p)) p++;
}
/* got it! */
}
Você começa a idéia. E, se há um caminho que corre mais rápido, eu não sei o que é.
Um caso de uso típico é semáforos.
Em uma nota implementação:. Enums do Java 5 pode ter métodos abstratos, que é uma excelente maneira de comportamento dependente do estado encapsular
