Дано множество двоичных слов X, оно разрешимо. Также есть множество двоичных слов Y, где у каждого слова некоторый префикс принадлежит множеству X. Разрешимо ли в таком случае множество Y?

задан 9 Фев 19:33

1

Да, разрешимо. Алгоритм проверки принадлежности множеству Y такой: берём слово, перебираем все его префиксы -- их конечное число. Для каждого из них при помощи разрешающей процедуры, которая есть по условию, проверяем принадлежность этого префикса множеству X. Если хотя бы для одного префикса ответ положительный, то анализируемое слово принадлежит Y. Если все ответы отрицательные, то не принадлежит.

(9 Фев 19:45) falcao

@falcao благодарю, я так же думал сделать

(9 Фев 19:47) FrostABC
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×494

задан
9 Фев 19:33

показан
251 раз

обновлен
9 Фев 19:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru