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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Перечисляющая программа для языка [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]


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