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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

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

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

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

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

[ Хронологический вид ]Ответы

(нет элементов)

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