Формально об алгоритмах. Вычислительные модели/Задачи/Разрешимость конкатенации

Материал из DISCOPAL
< Формально об алгоритмах. Вычислительные модели‎ | Задачи
Версия от 13:33, 11 октября 2020; StasFomin (обсуждение | вклад) (StasFomin переименовал страницу Формально об алгоритмах. Вычислительные модели/Разрешимость конкатенации в [[Формально об алгоритмах. Выч…)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

[ Хронологический вид ]Комментарии

Пусть слово w = ab, a /in L1, b /in L2.

Пусть |w| = n. Разбиваем w на подслова разными способами, запускаем первые подслова на машине, принимающей L1, если L1 выдала ДА, запускаем второе подслово на L2.

Рано или поздно разобьем слово на ab, обе машины скажут ДА, слово примется. Если слово не лежит в конкантенации, значит перебрав все варианты разбиения

не получим L1=1 && L2=1 - делаем вывод, что слово не принадлежит конкантенации.

Конкантенация разрешима

Войдите, чтобы комментировать.