Викиконспекты - Вклад участника [ru]

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

2010-12-01T20:48:02Z

Spolan:

{{Определение
|definition =
Перечисляющая программа для языка <tex>L</tex> - программа, по очереди выводящая все слова языка <tex>L</tex>. Если слово принадлежит языку, то программа за конечное время выдаст его на выходе. Слова, не принадлежащие языку, программа выводить не будет.
}}

{{Определение
|definition =
Полуразрешающая программа для языка <tex>L</tex> - программа, которая при подаче на вход слова из языка за конечное время завершится и вернет <tex>1</tex>, а при подаче на вход слова не из языка может за конечное время вернуть <tex>0</tex>, а может и зависнуть.
}}

{{Определение
|definition =
Перечислимый язык - язык, для которого существует перечисляющая программа.
}}

{{Определение
|definition =
Перечислимый язык - язык, для которого существует полуразрешающая программа.
}}

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

{{Теорема
|id=th1
|statement=
Два определения перечислимого языка эквивалентны.
|proof=
Пусть имеется перечисляющая программа для языка <tex>L</tex>, построим полуразрешающую. Сделаем это следующим образом. Получаем на вход некоторое слово <tex>w</tex>, запускаем перечисляющую программу. Если в процессе вывода слов встретится <tex>w</tex>, то завершаем работу, вернув <tex>1</tex>. Таким образом при подаче на вход слова из языка построенная программа вернет <tex>1</tex> и завершится. Если же мы подадим на вход слово не из языка, то построенная программа будет работать бесконечно долго, что вполне устраивает. Таким образом полуразрешающая программа построена.

Теперь пусть имеется полуразрешающая программа <tex>p</tex> для языка <tex>L</tex>, построим перечисляющую.

: for <tex>TL</tex> = <tex>1</tex> .. <tex>+\infty</tex> {
:: for <tex>length</tex> = <tex>1</tex> .. <tex>TL</tex> {
::: for <tex>w \in L</tex>, <tex>|w| = length</tex> {

:::: if <tex>p|_{TL}(w)=1</tex>
::::: выводим <tex>w</tex>;
:::}
::}
:}

Если слово <tex>w</tex> принадлежит языку, то условие <tex>p|_{TL}(w)=1</tex> будет выполнено для какого-то <tex>TL</tex>, а значит на выходе построенной программы рано или поздно появится <tex>w</tex>. Если же слово <tex>w</tex> не принадлежит языку, то <tex>p|_{TL}(w)=1</tex> ну будет выполнено ни для какого <tex>TL</tex>, а значит оно никогда не появится на выходе.

Таким образом мы построили перечисляющую программу.

В итоге теорема доказана.
}}

{{Теорема
|id=th2
|statement=
Любой разрешимый язык <tex>L</tex> является перечислимым.
|proof=
Язык <tex>L</tex> резрешимый, значит существует программа <tex>p</tex>, которая за конечное время определит, принадлежит ли поданное на вход слово языку <tex>L</tex>. Таким образом перечисляющая программа будет иметь следующий вид.

: for <tex>w \in L</tex> {

:: if <tex>p(w)=1</tex>
::: выводим <tex>w</tex>;
:}

Таким образом, на выходе появится слово <tex>w</tex> тогда и только тогда, когда <tex>w \in L</tex>, теорема доказана.
}}

{{Теорема
|id=th3
|statement=
Существуют перечислимые, но не разрешимые языки.
}}

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

2010-12-01T20:36:27Z

Spolan:

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

2010-12-01T20:20:31Z

Spolan:

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

2010-12-01T19:35:57Z

Spolan:

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

2010-11-29T18:38:00Z

Spolan: Новая страница: «{{Определение |definition = Детерминированная машина Тьюринга <tex>\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a\}\rangle<…»

{{Определение
|definition =
Детерминированная машина Тьюринга <tex>\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a\}\rangle</tex> допускает слово <tex>w\in \Sigma^{*}</tex>, если для некоторых <tex>m\in \mathbb{N}</tex> и <tex>n\in \mathbb{N}</tex> <tex>\langle \epsilon,q_s,b_0,w\rangle \vdash^{*}\langle b_0^{m},q_a,b_0,b_0^{n}\rangle</tex>
}}
{{Определение
|definition =
Язык, допускаемый машиной Тьюринга <tex>M</tex>, - это язык, состоящий из всех допускаемых данной машиной Тьюринга слов.
}}
{{Определение
|definition =
Язык называется <b>перечеслимым (рекурсивно перечислимым, полуразрешимым)</b>, если существует детерминированная машина Тьюринга, допускающая этот язык.
}}

{{Теорема
|id=th1
|statement=
Любой разрешимый язык является перечислимым.
|proof=
Пусть дана машина Тьюринга <tex>M=\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a, q_r\}\rangle</tex>, которая разрешает язык <tex>L</tex> тогда машина Тьюринга <tex>M'=\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a\}\rangle</tex> допускает язык <tex>L</tex>
}}