13 514
правок
Изменения
→Теория функциональных систем
==== Автоматы. Регулярные события и их представление в автоматах ====
==== Эксперименты с автоматами ====
* Берётся из {{Скачать|Алексеев - лекции по дискретной математике 2002.pdf}}.
* '''Т.''' (про отличимые состояния разных автоматов)
* '''Т.''' (о макс. длине эксп. отличающего состояния двух автоматов, +пример)
==== Алгоритмическая неразрешимость проблемы полноты для автоматов ====
* Берётся из {{Скачать|Мальцев - Алгоритмы и рекурсивные функции.djvu}}, стр. 254.
* '''Опр.''' полугруппа, система порождающих, определяющие соотношения, умножение классов.
* '''Опр.''' ассоциативного исчисления (набор замен); эквивалентные слова.
* '''Т.''' (Пост, Марков) {{exists}} ассоциативное исчисление с алгоритмически неразрешимой проблемой эквивалентности слов.
