Участница:Lyapustinamaria/Разрешимость конкатенации — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 12: Строка 12:
 
где P — множество всевозможных разбиений слова x на две подстроки
 
где P — множество всевозможных разбиений слова x на две подстроки
 
<latex>
 
<latex>
     if (p_1(x_1) == 1)\wedge (p_2(x_2) == 1)\\
+
\[
 +
     \mathrm{if} (p_1(x_1) == 1)\wedge (p_2(x_2) == 1)\\
 
       \mathrm{return} 1;\\
 
       \mathrm{return} 1;\\
 
   \mathrm{return} 0;\\
 
   \mathrm{return} 0;\\
 +
\]
 
</latex>
 
</latex>
  

Текущая версия на 13:26, 16 мая 2019

Решение

, — разрешимые языки. Их конкатенация так же будет разрешимой. Покажем это: Пусть , — разрешающие программы для языков , соответственно. Для доказательства достаточно написать разрешающую программу(разрешитель):

где P — множество всевозможных разбиений слова x на две подстроки

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова и второго слова .

Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит иначе — не принадлежит.

Источник: [1]
P.S. Если честно, меня очень смущает, что в одной вставке латех разные шрифты.

StasFomin 17:04, 15 мая 2019 (MSK): Тег «latex» обрабатывает содержимое латехом, но не переводит в math-mode (нужно еще и доллары). Для инлайн формул проще использовать компактный тег «m», вот как я частично подформатировал.