fundamentos fnd

MÁQUINAS DE ESTADO FINITO






Um computador armazena as informações internamente de forma binária. Sua memória interna contém algum padrão de dígitos binários, chamado estado do computador nesse momento. Um computador contém memória finita portanto  um número finito de estados
Quando uma entrada é lida (num ciclo do relógio interno que sincroniza as ações do computador) as posições de memória mudam gerando um novo estado. O que o novo estado representa depende tanto da entrada como do estado anterior.
Se a entrada e o estado forem conhecidos o novo estado é previsível e não aleatório.
O estado da máquina determina sua saída. Portanto ao fim de uma successão de ciclos do relógio, a máquina produz uma sequência de saídas em resposta a uma sequência de entradas. Definição
A máquina de estado finito é um modelo que retrata as características do computador descritas acima. Ao ler a definição perceba as seguintes propriedades:








as operações da máquina são sincronizadas por ciclos discretos do relógio a máquina procede de uma forma determinística, isto é, suas ações em resposta a uma dada sequência de entrada são completamente previsíveis. a máquina responde a entradas existe um número finito de estados que a máquina pode alcançar em qualquer momento a máquina está em um destes estados estado atual depende dos estados e entradas anteriores que por sua vez dependem também de seus estados e entradas anteriores e assim por diante até se chegar de volta à configuração inicial a máquina é capaz de produzir saídas cuja natureza é uma função do estado atual da máquina, o que significa que também depende das entradas anteriores.

Definição formal de máquina de estado finito:
M= [S,I,O,fs,fo] é uma máquina de estado finito se S for um conjunto finito de estados, I for um conjunto finito de símbolos de entrada (O alfabeto de entrada), O for o conjunto finito de saída
(o alfabeto de saída) e fs e fo forem funções