Участница:Lyapustinamaria/Разрешимость конкатенации

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

Решение

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

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

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

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

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

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