Учебники

Разрешимость языка

Язык называется Decidable или Recursive, если есть машина Тьюринга, которая принимает и останавливает каждую входную строку w . Каждый решаемый язык является приемлемым по Тьюрингу.

Решимость и решимость языков

Решение проблемы P разрешимо, если язык L всех экземпляров yes для P разрешим.

Для разрешимого языка, для каждой входной строки, TM останавливается либо в состоянии принятия, либо в состоянии отказа, как показано на следующей диаграмме –

Решаемый язык

Пример 1

Узнайте, разрешима ли следующая проблема –

Является ли число ‘m’ простым?

Решение

Простые числа = {2, 3, 5, 7, 11, 13, ………… ..}

Разделите число «m» на все числа от «2» до «√m», начиная с «2».

Если какое-либо из этих чисел выдает остаток ноль, то он переходит в «Отклоненное состояние», в противном случае он переходит в «Принятое состояние». Таким образом, здесь ответ может быть «Да» или «Нет».

Следовательно, это разрешимая проблема.

Пример 2

Учитывая регулярный язык L и строку w , как мы можем проверить, если w ∈ L ?

Решение

Возьмите DFA, который принимает L, и проверьте, принят ли w

DFA 1

Некоторые более решаемые проблемы –

  • Принимает ли DFA пустой язык?
  • Является ли L 1 ∩ L 2 = ∅ для регулярных множеств?

Примечание

Если язык L разрешим, то его дополнение L ‘ также разрешимо

Если язык разрешим, то для него есть перечислитель.