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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<latex> Пусть $L_1$ и $L_2$ - разрешимые языки. Является ли разрешимой их конкатенация? То есть $L_1L…»)
 
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 17 промежуточных версий 2 участников)
Строка 2: Строка 2:
 
Пусть $L_1$ и $L_2$ - разрешимые языки. Является ли разрешимой их конкатенация? То есть $L_1L_2 = \{ab \;|\; a \in L_1, b \in L_2\}$
 
Пусть $L_1$ и $L_2$ - разрешимые языки. Является ли разрешимой их конкатенация? То есть $L_1L_2 = \{ab \;|\; a \in L_1, b \in L_2\}$
 
\newline\newline
 
\newline\newline
Решение:
 
\newline\newline
 
Если язык разрешим, то существует МТ с полубесконечной лентой, разрешающая его: $M_1$ - разрешает $L_1$, $M_2$ - $L_2$.
 
Тогда конкатенацию будет разрешать следующая МТ с двумя лентами: будем записывать на первую ленту все возможные префиксы слова через пробел по порядку, на вторую - всевозможные суффиксы по порядку, и будем обрабатывать каждое из них по очереди машинами M_1 и M_2(это получится, поскольку они работают с полубесконечной лентов, то есть двигаются в одну сторону, а оставшиеся префиксы/суффиксы находятся другой). Алгоритм работы такой: запускаем на первой ленте M_1, которая при этом недвигается по второй ленте. Если $M_1$ выдала $1$, то запускаем $M_2$: если $1$, то ура мы нашли слово из конкатенации; если одна из них выдаёт $0$, то чистим текущий префикс/суффикс и переходим к следующим. Если мы прочитали всё (словили два пробела подряд), значит слово не принадлежит конкатенации, выводим $0$ и переходим в финальное состояние. То есть мы построили заведомо останавливающуюся машину Тьюринга, значит конкатенация разрешимых языков разрешима.
 
 
P.S. Если фантазировать дальше, то можно задать вопрос: является ли конкатенация P языков P языком ит.д. В принципе идея та же самая: если машина Тьюринга работает за полином, значит эквивалентная ей машина с полубесконечной лентой тоже работает за полином(пути увеличиваются в два раза). У слова n префиксов и суффиксов, значит мы каждую машину запустим n раз, то есть все равно получим в итоге машину, которая работает за полином.
 
 
</latex>
 
</latex>
  
[[Категория:Предложенные студентами задачи]]
+
[[Категория:Решенные задачи]]
 +
[[Категория:Теоретические задачи]]

Текущая версия на 06:50, 4 мая 2023