Теорема Мура и Клини

jeni

Народ подскажите формулировку теоремы Мура об отличимости состояний и теоремы Клини о представлении.
(Теоремы об автоматах)

Pashkaspk

Теорема Клини: состояние представимо т.и.т.т оно регулярно.
Теорема Мура: состояния в автомате длины <=n отличимы т.и.т.т. они отличимы на слове длины <=n-1.

sasha_m

За точность не ручаюсь:
Теорема Мура
Для проверки двух автоматов на различие достаточно проверить все слова входного алфавита длиной: (кол-во состояний первого автомата) + (кол-во состояний второго автомата) + 1.

jeni

А что значит что состояние регулярно?
И насчет теоремы Мура ты уверен?

sasha_m

И насчет теоремы Мура ты уверен?

Я лишь не уверен в знаке +/- 1. А так вроде верно.

Pashkaspk

-1. И вроде это не та теорема которая Буху нужна, ему нужно именно для одного автомата.

Ner83

У теоремы Клини об автоматных языках есть несколько эквивалентных формулировок:)
Если Бух это тот Бух, о котором я думаю, то он наверняка слышал её в другой формулировке:)

sasha_m

И вроде это не та теорема которая Буху нужна, ему нужно именно для одного автомата.

Возможно, но он не уточнял для скольких автоматов ему надо.

Pashkaspk

Бух тот самый, я не уверен что он вообще раньше эту теорему слышал

Ner83

А чего, у вас Борисенка не читал чтоль курсе на втором всю эту автоматную пургу?

dimaxd

Кстати да. Теорему Клини можно посмотреть (в контексте) в электронной версии лекций Борисенко, тут: http://student.math.msu.su/2course/Borisenko/lect11.html

gelenada

Борисенко у них наверное ничего вообще не читал

Ner83

По ходу
А то в его исполнении теорему Клини трудно запамятовать:)

Pashkaspk

нет не читал
Оставить комментарий
Имя или ник:
Комментарий: