Машины Мура с n состояниями

Я работаю над вопросом в конце главы о том, сколько существует различных машин Мура с n состояниями. Где n = количество состояний, m = количество входных букв и q = количество выходных символов, верно ли, что существует n*q^m возможных машин? Я полагаю, что для каждого состояния каждый ввод может привести к одному из заданных выходных символов.


finite-automata
person user3705359    schedule 07.02.2016    source источник
comment
Когда вы считаете две машины Мура идентичными? Когда у них один и тот же вывод для каждого входа? Или модель должна быть идентичной?   -  person Ctx    schedule 08.02.2016
comment
Машины Мура идентичны, если они имеют одинаковый выход для каждого входа.   -  person user3705359    schedule 08.02.2016
comment
Уверены ли вы? Я думаю, что в этом случае было бы очень сложно решить (если вообще)   -  person Ctx    schedule 08.02.2016
comment
Вопрос просто говорит: исходя из табличного представления для машин Мура, сколько существует различных машин с n состояниями.   -  person user3705359    schedule 08.02.2016
comment
Хорошо, это означает, сколько разных моделей существует (где две или более могут иметь одинаковый результат). Это не так сложно.   -  person Ctx    schedule 08.02.2016

Ответы (1)


arrow_upward
1
arrow_downward

Машина Мура состоит из:

  • множество состояний S (n)
  • начальное состояние s0
  • ввод алфавита Сигма (м)
  • выходной алфавит A (q)
  • функция перехода (S x Sigma -> S)
  • выходная функция (S -> A)

Задается количество состояний и входных/выходных символов.

Для начального состояния существует n вариантов.

Для функции перехода есть |S| ^ (|S| * |Sigma|) = n^(n*m) разные варианты.

Наконец, есть |A| ^ |С| = q^n функции вывода

Всего получается n^(n*m+1) * q^n различных машин Мура.

person Ctx    schedule 07.02.2016