Перечислимые языки

Определение:

Перечисляющая программа для языка [math]L[/math] - программа, по очереди выводящая все слова языка [math]L[/math]. Если слово принадлежит языку, то программа за конечное время выдаст его на выходе. Слова, не принадлежащие языку, программа выводить не будет.

Определение:

Полуразрешающая программа для языка [math]L[/math] - программа, которая при подаче на вход слова из языка за конечное время завершится и вернет [math]1[/math], а при подаче на вход слова не из языка может за конечное время вернуть [math]0[/math], а может и зависнуть.

Определение:

Перечислимый язык - язык, для которого существует перечисляющая программа.

Определение:

Перечислимый язык - язык, для которого существует полуразрешающая программа.

Определение:

Пусть имеется некоторая программа [math]p[/math], которая может либо завершиться за конечное время и что-то вернуть, либо зависнуть. Тогда запуск программы [math]p[/math] с тайм-лимитом [math]TL[/math] будем обозначать как [math]p|_{TL}[/math] и иметь в виду следующее: если за [math]TL[/math] операций программа [math]p[/math] корректно завершилась и что-то вернула, то [math]p|_{TL}[/math] вернет то же самое; если же за [math]TL[/math] операций программа [math]p[/math] не успела завершиться, то [math]p|_{TL}[/math] вернет [math]\bot[/math] (специально зарезервированное значение).

Теорема:

Два определения перечислимого языка эквивалентны.

Доказательство:

[math]\triangleright[/math]

Пусть имеется перечисляющая программа для языка [math]L[/math], построим полуразрешающую. Сделаем это следующим образом. Получаем на вход некоторое слово [math]w[/math], запускаем перечисляющую программу. Если в процессе вывода слов встретится [math]w[/math], то завершаем работу, вернув [math]1[/math]. Таким образом при подаче на вход слова из языка построенная программа вернет [math]1[/math] и завершится. Если же мы подадим на вход слово не из языка, то построенная программа будет работать бесконечно долго, что вполне устраивает. Таким образом полуразрешающая программа построена. Теперь пусть имеется полуразрешающая программа [math]p[/math] для языка [math]L[/math], построим перечисляющую. for [math]TL[/math] = [math]1[/math] .. [math]+\infty[/math] { for [math]length[/math] = [math]1[/math] .. [math]TL[/math] { for [math]w \in L[/math], [math]|w| = length[/math] { if [math]p|_{TL}(w)=1[/math] выводим [math]w[/math]; } } } Если слово [math]w[/math] принадлежит языку, то условие [math]p|_{TL}(w)=1[/math] будет выполнено для какого-то [math]TL[/math], а значит на выходе построенной программы рано или поздно появится [math]w[/math]. Если же слово [math]w[/math] не принадлежит языку, то [math]p|_{TL}(w)=1[/math] ну будет выполнено ни для какого [math]TL[/math], а значит оно никогда не появится на выходе. Таким образом мы построили перечисляющую программу. В итоге теорема доказана.

[math]\triangleleft[/math]

Теорема:

Любой разрешимый язык [math]L[/math] является перечислимым.

Доказательство:

[math]\triangleright[/math]

Язык [math]L[/math] резрешимый, значит существует программа [math]p[/math], которая за конечное время определит, принадлежит ли поданное на вход слово языку [math]L[/math]. Таким образом перечисляющая программа будет иметь следующий вид. for [math]w \in L[/math] { if [math]p(w)=1[/math] выводим [math]w[/math]; } Таким образом, на выходе появится слово [math]w[/math] тогда и только тогда, когда [math]w \in L[/math], теорема доказана.

[math]\triangleleft[/math]

Теорема:

Существуют перечислимые, но не разрешимые языки.