Como uma máquina de estado é diferente de qualquer outro programa de computador?

Eu já vi várias implementações de "State Machines" no github. Tanto quanto eu entendo, uma máquina de estados recebe entradas que podem ou não transformar seu estado em um de um conjunto finito de outros estados. Como isso é diferente de qualquer outro programa de computador?

Se você quer ser realmente pedante, todo programa de computador é uma Máquina de Estado Finito, porque mesmo que você converta toda a matéria do universo inteiro em um computador, ele ainda terá apenas memória finita, portanto, uma quantidade finita de estados e uma quantidade finita. quantidade de transições entre esses estados.

Máquinas de estado são modelos, assim como Cálculo Lambda, Máquinas de Turing, Máquinas de acesso aleatório, Sistemas de atores, Sistemas de objetos e assim por diante. Alguns problemas se prestam a serem modelados por uma máquina de estado, outros não.

Os processos de negócios eram frequentemente modelados como máquinas de estado antes mesmo da existência de computadores. Eles se prestam naturalmente a esse tipo de pensamento.

Do ponto de vista teórico, não é diferente. Obviamente, do ponto de vista teórico, você pode escrever qualquer programa em linguagem assembly e ele também funcionará.

Enquanto o computador em que seu código está sendo executado pode ser matematicamente equivalente a uma máquina de estados muito, muito complicada, assim como qualquer outro programa executado em qualquer outro computador, existem muitos problemas cuja solução mais elegante é uma máquina de estados finitos simples cujos estados e As transições têm significados específicos de domínio que o programador criou (em oposição ao compilador ou ao designer de hardware).

Por exemplo, uma maneira clássica de implementar expressões regulares é interpretar a expressão regular como uma especificação para uma máquina de estados finitos, construí-la e alimentá-la para aceitar ou rejeitar . De maneira mais geral, sempre que você deseja que um objeto em seu programa sempre tenha um número finito de estados e imponha que as transições entre esses estados sempre ocorram de maneiras específicas, construir uma máquina de estados pode ser a solução mais elegante .

uma máquina de estados recebe entradas que podem ou não transformar seu estado em um conjunto finito de outros estados. Como isso é diferente de qualquer outro programa de computador?

Algumas respostas aqui enfatizam que em nosso universo (provavelmente) finito tudo é finito, todos os programas de computador são executados em tempo finito; portanto, tecnicamente, tudo é uma máquina de estado finito. Isso é "tecnicamente correto (o melhor tipo de correção)", mas também está completamente errado.

A essência é a seguinte: - Alguns programas de computador exigem mais memória de trabalho quando obtêm entradas maiores e mais complexas. Alguns não.

Se você perceber isso, obterá uma visão teórico-informativa que poderá permitir que você escreva programas mais eficientes e elegantes quando encontrar o tipo de problema especificado. Também permitirá que você reconheça o tipo de problema em que isso pode se aplicar.

Aqui estão dois exemplos de brinquedos:

Problema 1: Um programa recebe uma lista de caracteres na entrada padrão. Após o processamento de todos os caracteres, o programa deve imprimir se o número de caracteres "x" na entrada foi ímpar ou par .

Problema 2: Um programa recebe uma lista de caracteres na entrada padrão. Após o processamento de todos os caracteres, o programa deve imprimir se o número de caracteres "x" na entrada foi menor , igual ou maior que o número de caracteres "y".

Você pode parar de ler agora, resolver os problemas em sua linguagem de programação favorita (ou apenas um pseudocódigo) e retornar mais tarde.

...

O importante que você deve ter notado é o seguinte: Para implementar a solução do problema 1 corretamente, você precisa apenas de um pouco de memória. Você não precisa calcular quantos "x" já processou - apenas se o número de "x" processados ​​até agora foi ímpar ou par. Quando você encontrar outro "x", vire o bit. No final do programa, observe a parte e imprima a resposta.

Sua entrada contém uma dúzia de caracteres? Milhares de personagens? Personagens Googolplex (hipoteticamente falando, é claro)? Não importa; um pouco de memória de trabalho ainda será suficiente.

Você não pode fazer a mesma coisa com o problema 2. Ao ler os caracteres, lembre-se da diferença entre o número de "x" 's e "y" já processados; caso contrário, você não poderá imprimir a resposta correta de maneira confiável. Você pode perceber que você realmente não precisa se lembrar de ambos os números de "x" 's e 'y'' s - apenas a sua diferença, até agora; um valor inteiro que você aumentará quando encontrar outro "x" e diminuirá quando encontrar outro "y" - mas ainda assim, se você decidir usar, por exemplo, 32 bits de memória para manter esse valor, poderá receber uma entrada ( bilhões de caracteres) que você não pode processar corretamente com a quantidade limitada de memória.

É isso o que queremos dizer com dizer que o problema 1 pode ser resolvido por uma "máquina de estado" e o problema 2 não. Uma quantidade limitada de memória é suficiente para uma entrada de qualquer tamanho.

(Obviamente, você também pode escrever uma solução ineficiente para o problema 1, onde tentaria contar todos os "x" 's e, em seguida, também obteria um problema de falta de memória. Mas a diferença é que um existe uma solução eficiente para o problema 1 , enquanto uma solução igualmente eficiente para o problema 2 não existe .)

Por que isso é importante na vida real?

Primeiro, diferentemente desses dois exemplos de brinquedos, o dilema pode não estar literalmente entre um bit e um valor inteiro, mas entre uma estrutura de dados grande e outra ainda maior. Às vezes, a estrutura de dados "ainda maior" não se encaixa na memória do computador ou reduz a velocidade do programa, mesmo para entradas realistas.

Segundo, a solução que usa a máquina de estado provavelmente será muito mais rápida. Também será dimensionado linearmente com o comprimento da entrada; isto é, o processamento de entrada 10 vezes mais exigirá 10 vezes mais tempo (em oposição a, por exemplo, 100 vezes mais tempo). Essa é uma propriedade desejada quando você precisa processar muitos dados.

Terceiro, o uso limitado e ilimitado de memória afeta a segurança . Se você escreve um programa que requer apenas memória limitada, não precisa se preocupar com o excesso de memória e como eles podem ser abusados ​​para comprometer a segurança de todo o sistema.

Quarto, isso faz parte do que deveria ser um currículo padrão de ciência da computação em qualquer escola decente: línguas formais , automatos , complexidade computacional etc. Para entender o panorama geral por trás do design do computador, em vez de apenas "uhh, juntei alguns códigos da internet, espero realmente que funcione, mas não sei ao certo".

Para tirar proveito dessa teoria, você realmente não precisa de nenhuma máquina especial, de qualquer estrutura ou biblioteca ... você só precisa entender "oh, essa parte do problema pode realmente ser resolvida usando uma quantidade finita de memória" e escrever seu programa (na sua linguagem de programação favorita) de acordo. Mas, em algumas situações, é melhor usar uma biblioteca existente, para que você não precise reinventar a roda.

Como as outras respostas apontaram, não há nada de especial nas máquinas de estado. No entanto, é frequentemente benéfico afirmar explicitamente que nosso programa implementa um FSM.

A programação consiste em encontrar muitas abstrações adequadas para um problema. Usar uma abstração implica falar em termos da abstração e não em termos da implementação. Muitos processos são inerentemente com estado, por exemplo, o processo de inscrição em um site ou o processo de check-out em um aplicativo de comércio eletrônico. Se eu modelasse esses processos, desenharia caixas conectadas por setas em um quadro branco - um diagrama de estados. Aqui, uma máquina de estado seria um tipo de padrão de design e falar sobre máquinas de estado comunicaria claramente minha intenção aos colegas.

Programas imperativos são inerentemente com estado, portanto nem sempre percebemos quando introduzimos o estado. Por exemplo, na linguagem C, certas construções de linguagem, como o operador de ponto e vírgula, marcam um "ponto de sequência", que é uma transição de estado e impõe a ordem entre operações. As coisas são diferentes em ambientes como linguagens funcionais puras, como Haskell, ou ao usar protocolos sem estado, como HTTP. De repente, qualquer estado deve se tornar explícito, e redigir explicitamente nosso design como uma máquina de estado pode torná-lo mais gerenciável.

Máquinas de estados finitos desempenham um papel importante na análise, pois correspondem a expressões regulares. A implementação manual de alguma expressão regular pode resultar em um código extremamente cabeludo, que na pior das hipóteses nem é correto. Quando percebemos que estamos implementando uma máquina de estado, podemos usar uma variedade de técnicas de implementação conhecidas para nos ajudar. Por exemplo, poderíamos tornar o estado explícito e armazenar o estado atual em uma variável. Como alternativa, podemos tornar o estado implícito através do fluxo de controle em nossa linguagem. Fiz as duas coisas em circunstâncias diferentes, mas afirmar que estamos implementando uma máquina de estado (que apresenta transições de estado restritas, um estado inicial, estados finais conhecidos, sem recursão e nenhum estado implícito por meio da alocação persistente de dados) em vez de um programa irrestrito mais fácil de implementar e entender.

Eu raramente usaria uma biblioteca de máquinas de estado, pois todas as linguagens de programação que conheço facilitam a expressão correta e eficiente de uma máquina de estado nessa linguagem. Mas há exceções: embora os autômatos determinísticos sejam fáceis de implementar, os autômatos não determinísticos são bastante triviais, pois a máquina de estados pode estar em vários estados ao mesmo tempo. O uso de uma biblioteca que implementa NFAs ou as reescreve, permite que eu ignore essas dificuldades e me concentre nas coisas que realmente importam.

Além dos usos das máquinas de estado como design e máquinas de estado na ciência da computação e na teoria da linguagem, não existem realmente muitos usos. Circuitos lógicos com estado vêm à mente. O principal uso de máquinas de estado para um programador é aprender a pensar em termos de estados e transições de estado. Onde meu programa tem estados implícitos? Eu implementei corretamente todas as transições de estado? Perdi alguma coisa e abri um estado inválido? Esse pensamento se torna especialmente relevante novamente na programação orientada a objetos, uma vez que os campos membros de um objeto correspondem ao estado, e os métodos podem efetuar transições de estado. Eu hesitaria em implementar explicitamente uma máquina de estado em um objeto, mas uma máquina de estado pode, no entanto, ser um modelo mental adequado para o comportamento.

O principal motivo para escrever uma biblioteca de máquinas de estado é certificar-se de que você entendeu o tópico, mas na maioria dos aplicativos você não precisaria deles ou melhor, rolaria manualmente.