Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
Версия от 05:31, 19 декабря 2011; Roman Livarsky (обсуждение | вклад)
Теорема: |
Языки –- разрешимы, тогда языки
|
Доказательство: |
Пусть и — разрешающие программы для языков и соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.
return
return
return
return
return
forall разбиение if then return 1 return 0 Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность . Если хотя бы в одном разбиении все подслова будут принадлежать , то все слово принадлежит , иначе — не принадлежит.
Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова forall разбиение if then return 1 return 0 и второго слова . Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит , иначе — не принадлежит. |
Теорема: |
Языки –- перечислимы, тогда языки
|
Доказательство: |
Пусть и — полуразрешающие программы для языков и соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Для некоторых языков предоставим оба варианта. Заметим, что и могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.
полуразрешающая программа: if then return 1 Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для и и выдавать по очереди слова из и соответственно.
полуразрешающая программа: if then return 1
полуразрешающая программа: if then return 1
полуразрешающая программа (по аналогии с для разрешимого ):forall разбиение if then return 1 Перечислитель строится следующим образом: запускаем перечислитель для в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.
полуразрешающая программа: Перечислитель для forall разбиение if then return 1 строим следующим образом: запускаем одновременно перечислители для и , запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию. |
Теорема: |
Языки –- перечислимы, тогда языки
|
Доказательство: |
Рассмотрим язык Теперь рассмотрим . Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для и . В какой-то момент времени слово появится либо в выводе перечислителя для , либо в выводе перечислителя для . Тогда получится что разрешим, так как про любое слово мы можем узнать принадлежит оно или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык может быть не перечислим. . В качестве возьмем язык, состоящий из всех слов. Тогда получится, что язык это . Про язык мы знаем, что он перечислим не всегда, следовательно и язык также не всегда перечислим. |
Литература
- Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции -- М.: МЦНМО, 1999