|
|
| Строка 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> |
| | | | |
| | [[Категория:Предложенные студентами задачи]] | | [[Категория:Предложенные студентами задачи]] |