Конечные автоматы: количество возможных ответов

Question

Мне интересно, существует ли уравнение, которое дает число возможных конфигураций любого данного конечного автомата, созданного для обработки n входов и m состояний.

Сколько возможных решений существует для любого данного процесса при использовании конечного автомата для его описания?

Я спрашиваю, потому что у меня есть проблема, которую нужно решить с помощью конечных автоматов, и я хочу знать, есть ли только одно возможное решение или много.

[Проблема]

Создайте конечный автомат, который выдает результат 1, если вход X, который может принимать значение 0 или 1, был 101 за последние три такта. Х обновляется каждый такт. Существует четыре возможных состояния S0, S1, S2 и S3.

Answer 1

Количество конфигураций в FSM - это число состояний. У него нет памяти или контекста, чтобы отличить состояние "сейчас в состоянии X" от состояния "тогда в состоянии X".

Вы говорите о потенциальных путях через штаты? то есть выходную последовательность, которую он излучает при переходе или, что эквивалентно, входы, которые приводят к состоянию завершения? Они потенциально бесконечны, в зависимости от машины.

Автоматы очень и очень простые. Если вы не уверены, что можете их использовать, возможно, у вас нет четкого описания проблемы.

В чем собственно проблема?