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

M-сводимость

2016-12-01T20:34:50Z

5.18.224.199: /* Применение */

{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (англ. ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (англ. ''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Свойства ==
# <tex>A\leqslant_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
#*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.

== Применение ==
{{Лемма
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.

К таким задачам относятся, например, [[Примеры неразрешимых задач: проблема соответствий Поста|проблема соответствий Поста]], [[Примеры неразрешимых задач: задача о замощении|задача о замощении полимино]] и другие .

==Сведение по Тьюрингу==
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
}}

{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (англ. ''Turing equivalent'') языку <tex>M</tex>, если <tex>L \leqslant_T M</tex> и <tex>M \leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}

=== Свойства ===
* рефлексивность: <tex> L \leqslant_T L </tex>
* транзитивность: из <tex> L \leqslant_T M </tex> и <tex> M \leqslant_T N</tex> следует <tex> L \leqslant_T N </tex>
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности

=== Т-степени ===

Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством <tex>T</tex>-степеней (тьюринговых степеней).

{{Определение
|definition=
<tex>T</tex>-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
}}

На <tex>T</tex>-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя <tex>T</tex>-степени.

==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на <tex>T</tex>-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара <tex>T</tex>-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.

==== Тьюринговый скачок ====
Обозначим за <tex>H</tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, использующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

* <tex>f <_T H^f</tex>
* Если <tex>f \leqslant_T g</tex>, то <tex>H^f \leqslant_T H^g</tex>

Тогда тьюринговым скачком <tex>T</tex>-степени <tex>d</tex> называется <tex>T</tex>-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.

== Источники информации ==
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''Верещагин Н., Шень А.'' Вычислимые функции, 2-е изд. — МЦНМО, 2002. — С. 64. — ISBN 5-900916-36-7
* ''P. Odifreddi'' — Classical recursion theory. — Elsivier, 1992. — ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач]]

M-сводимость

2016-11-22T11:59:40Z

5.18.224.199: /* Источники информации */

{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (англ. ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (англ. ''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Свойства ==
# <tex>A\leqslant_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
#*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.

== Применение ==
{{Лемма
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.

Например, [[Примеры неразрешимых задач: проблема соответствий Поста|проблема соответствий Поста]].

==Сведение по Тьюрингу==
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
}}

{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (англ. ''Turing equivalent'') языку <tex>M</tex>, если <tex>L \leqslant_T M</tex> и <tex>M \leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}

=== Свойства ===
* рефлексивность: <tex> L \leqslant_T L </tex>
* транзитивность: из <tex> L \leqslant_T M </tex> и <tex> M \leqslant_T N</tex> следует <tex> L \leqslant_T N </tex>
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности

=== Т-степени ===

Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством <tex>T</tex>-степеней (тьюринговых степеней).

{{Определение
|definition=
<tex>T</tex>-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
}}

На <tex>T</tex>-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя <tex>T</tex>-степени.

==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на <tex>T</tex>-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара <tex>T</tex>-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.

==== Тьюринговый скачок ====
Обозначим за <tex>H</tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, использующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

* <tex>f <_T H^f</tex>
* Если <tex>f \leqslant_T g</tex>, то <tex>H^f \leqslant_T H^g</tex>

Тогда тьюринговым скачком <tex>T</tex>-степени <tex>d</tex> называется <tex>T</tex>-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.

== Источники информации ==
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''Верещагин Н., Шень А.'' Вычислимые функции, 2-е изд. — МЦНМО, 2002. — С. 64. — ISBN 5-900916-36-7
* ''P. Odifreddi'' — Classical recursion theory. — Elsivier, 1992. — ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач]]

M-сводимость

2016-11-22T11:45:55Z

5.18.224.199: /* Т-степени */

{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (англ. ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (англ. ''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Свойства ==
# <tex>A\leqslant_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
#*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.

== Применение ==
{{Лемма
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.

Например, [[Примеры неразрешимых задач: проблема соответствий Поста|проблема соответствий Поста]].

==Сведение по Тьюрингу==
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
}}

{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (англ. ''Turing equivalent'') языку <tex>M</tex>, если <tex>L \leqslant_T M</tex> и <tex>M \leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}

=== Свойства ===
* рефлексивность: <tex> L \leqslant_T L </tex>
* транзитивность: из <tex> L \leqslant_T M </tex> и <tex> M \leqslant_T N</tex> следует <tex> L \leqslant_T N </tex>
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности

=== Т-степени ===

Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством <tex>T</tex>-степеней (тьюринговых степеней).

{{Определение
|definition=
<tex>T</tex>-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
}}

На <tex>T</tex>-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя <tex>T</tex>-степени.

==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на <tex>T</tex>-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара <tex>T</tex>-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.

==== Тьюринговый скачок ====
Обозначим за <tex>H</tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, использующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

* <tex>f <_T H^f</tex>
* Если <tex>f \leqslant_T g</tex>, то <tex>H^f \leqslant_T H^g</tex>

Тогда тьюринговым скачком <tex>T</tex>-степени <tex>d</tex> называется <tex>T</tex>-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.

== Источники информации ==
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''Верещагин Н., Шень А.'' Вычислимые функции, 2-е изд. — МЦНМО, 2002. — С. 64. — ISBN 5-900916-36-7
* ''P. Odifreddi'' — Classical recursion theory. — Elsivier, 1992. — ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}

M-сводимость

2016-11-22T11:40:31Z

5.18.224.199: /* Сведение по Тьюрингу */

{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (англ. ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (англ. ''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Свойства ==
# <tex>A\leqslant_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
#*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.

== Применение ==
{{Лемма
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.

Например, [[Примеры неразрешимых задач: проблема соответствий Поста|проблема соответствий Поста]].

==Сведение по Тьюрингу==
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (англ. ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
}}

{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (англ. ''Turing equivalent'') языку <tex>M</tex>, если <tex>L \leqslant_T M</tex> и <tex>M \leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}

=== Свойства ===
* рефлексивность: <tex> L \leqslant_T L </tex>
* транзитивность: из <tex> L \leqslant_T M </tex> и <tex> M \leqslant_T N</tex> следует <tex> L \leqslant_T N </tex>
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности

=== Т-степени ===

Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством Т-степеней (тьюринговых степеней).

{{Определение
|definition=
Т-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
}}

На Т-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степени.

==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на Т-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара Т-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.

==== Тьюринговый скачок ====
Обозначим за <tex>H</tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, использующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

* <tex>f <_T H^f</tex>
* Если <tex>f \leqslant_T g</tex>, то <tex>H^f \leqslant_T H^g</tex>

Тогда тьюринговым скачком Т-степени <tex>d</tex> называется Т-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.

== Источники информации ==
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''Верещагин Н., Шень А.'' Вычислимые функции, 2-е изд. — МЦНМО, 2002. — С. 64. — ISBN 5-900916-36-7
* ''P. Odifreddi'' — Classical recursion theory. — Elsivier, 1992. — ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}

M-сводимость

2016-11-22T11:39:45Z

5.18.224.199:

{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (англ. ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (англ. ''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Свойства ==
# <tex>A\leqslant_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
#*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.

== Применение ==
{{Лемма
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.

Например, [[Примеры неразрешимых задач: проблема соответствий Поста|проблема соответствий Поста]].

==Сведение по Тьюрингу==
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (является ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
}}

{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (''Turing equivalent'') языку <tex>M</tex>, если <tex>L \leqslant_T M</tex> и <tex>M \leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}

=== Свойства ===
* рефлексивность: <tex> L \leqslant_T L </tex>
* транзитивность: из <tex> L \leqslant_T M </tex> и <tex> M \leqslant_T N</tex> следует <tex> L \leqslant_T N </tex>
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности

=== Т-степени ===

Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством Т-степеней (тьюринговых степеней).

{{Определение
|definition=
Т-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
}}

На Т-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степени.

==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на Т-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара Т-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.

==== Тьюринговый скачок ====
Обозначим за <tex>H</tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, использующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

* <tex>f <_T H^f</tex>
* Если <tex>f \leqslant_T g</tex>, то <tex>H^f \leqslant_T H^g</tex>

Тогда тьюринговым скачком Т-степени <tex>d</tex> называется Т-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.

== Источники информации ==
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''Верещагин Н., Шень А.'' Вычислимые функции, 2-е изд. — МЦНМО, 2002. — С. 64. — ISBN 5-900916-36-7
* ''P. Odifreddi'' — Classical recursion theory. — Elsivier, 1992. — ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}

M-сводимость

2016-11-21T19:56:16Z

5.18.224.199: /* Применение */

{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (является ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Свойства ==
# <tex>A\leqslant_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
#*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.

== Применение ==
{{Лемма
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.

Например, [[Примеры неразрешимых задач: проблема соответствий Поста|проблема соответствий Поста]].

==Сведение по Тьюрингу==
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (является ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
}}

{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (''Turing equivalent'') языку <tex>M</tex>, если <tex>L \leqslant_T M</tex> и <tex>M \leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}

=== Свойства ===
* рефлексивность: <tex> L \leqslant_T L </tex>
* транзитивность: из <tex> L \leqslant_T M </tex> и <tex> M \leqslant_T N</tex> следует <tex> L \leqslant_T N </tex>
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности

=== Т-степени ===

Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством Т-степеней (тьюринговых степеней).

{{Определение
|definition=
Т-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
}}

На Т-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степени.

==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на Т-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара Т-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.

==== Тьюринговый скачок ====
Обозначим за <tex>H</tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, использующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

* <tex>f <_T H^f</tex>
* Если <tex>f \leqslant_T g</tex>, то <tex>H^f \leqslant_T H^g</tex>

Тогда тьюринговым скачком Т-степени <tex>d</tex> называется Т-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.

== Источники информации ==
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''Верещагин Н., Шень А.'' Вычислимые функции, 2-е изд. — МЦНМО, 2002. — С. 64. — ISBN 5-900916-36-7
* ''P. Odifreddi'' — Classical recursion theory. — Elsivier, 1992. — ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}

M-сводимость

2016-11-21T19:51:33Z

5.18.224.199: /* Литература */

{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (является ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Свойства ==
# <tex>A\leqslant_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
#*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.

== Применение ==
{{Лемма
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.

Например:
* [[Примеры неразрешимых задач: проблема соответствий Поста|неразрешимость проблемы соответствий Поста]].

==Сведение по Тьюрингу==
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (является ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
}}

{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (''Turing equivalent'') языку <tex>M</tex>, если <tex>L \leqslant_T M</tex> и <tex>M \leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}

=== Свойства ===
* рефлексивность: <tex> L \leqslant_T L </tex>
* транзитивность: из <tex> L \leqslant_T M </tex> и <tex> M \leqslant_T N</tex> следует <tex> L \leqslant_T N </tex>
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности

=== Т-степени ===

Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством Т-степеней (тьюринговых степеней).

{{Определение
|definition=
Т-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
}}

На Т-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степени.

==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на Т-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара Т-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.

==== Тьюринговый скачок ====
Обозначим за <tex>H</tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, использующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

* <tex>f <_T H^f</tex>
* Если <tex>f \leqslant_T g</tex>, то <tex>H^f \leqslant_T H^g</tex>

Тогда тьюринговым скачком Т-степени <tex>d</tex> называется Т-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.

== Источники информации ==
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''Верещагин Н., Шень А.'' Вычислимые функции, 2-е изд. — МЦНМО, 2002. — С. 64. — ISBN 5-900916-36-7
* ''P. Odifreddi'' — Classical recursion theory. — Elsivier, 1992. — ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}

M-сводимость

2016-11-21T19:36:51Z

5.18.224.199: /* Т-степени */

{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (является ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Свойства ==
# <tex>A\leqslant_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
#*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.

== Применение ==
{{Лемма
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.

Например:
* [[Примеры неразрешимых задач: проблема соответствий Поста|неразрешимость проблемы соответствий Поста]].

==Сведение по Тьюрингу==
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (является ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
}}

{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (''Turing equivalent'') языку <tex>M</tex>, если <tex>L \leqslant_T M</tex> и <tex>M \leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}

=== Свойства ===
* рефлексивность: <tex> L \leqslant_T L </tex>
* транзитивность: из <tex> L \leqslant_T M </tex> и <tex> M \leqslant_T N</tex> следует <tex> L \leqslant_T N </tex>
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности

=== Т-степени ===

Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством Т-степеней (тьюринговых степеней).

{{Определение
|definition=
Т-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
}}

На Т-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \leqslant d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степени.

==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на Т-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара Т-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.

==== Тьюринговый скачок ====
Обозначим за <tex>H</tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, использующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

* <tex>f <_T H^f</tex>
* Если <tex>f \leqslant_T g</tex>, то <tex>H^f \leqslant_T H^g</tex>

Тогда тьюринговым скачком Т-степени <tex>d</tex> называется Т-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.

== Литература ==
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''Верещагин Н., Шень А.'' — '''Вычислимые функции''', 2-е изд. МЦНМО, 2002, стр. 64. ISBN 5-900916-36-7
* ''P. Odifreddi'' — '''Classical recursion theory'''. Elsivier, 1992. ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}

M-сводимость

2016-11-21T19:33:42Z

5.18.224.199:

{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (является ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\leqslant_{m}B</tex>.
}}
{{Определение
|definition=<tex>A</tex> '''m-эквивалентно''' (''many-one equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.
}}
== Свойства ==
# <tex>A\leqslant_{m}A</tex>.
#*'''Доказательство:''' <tex>f(x)=x</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> разрешимо, то <tex>A</tex> разрешимо.
#*'''Доказательство:''' Пусть <tex>p</tex> — программа-разрешитель для <tex>B</tex>. Тогда для любого <tex>x\in A</tex> разрешитель должен вернуть значение <tex>p(f(x))</tex>.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B</tex> перечислимо, то <tex>A</tex> перечислимо.
#*'''Доказательство:''' Аналогично предыдущему свойству.
# Если <tex>A\leqslant_{m}B</tex> и <tex>B\leqslant_{m}C</tex>, то <tex>A\leqslant_{m}C</tex>.
#*'''Доказательство:''' Если <tex>f:A\to B</tex> и <tex>g:B\to C</tex>, то m-сводящая функция <tex>h:A\to C</tex> выглядит так <tex>h(x) = g(f(x))</tex>.

== Применение ==
{{Лемма
|statement=
Если <tex>A\leqslant_{m}B</tex> и <tex>A</tex> неразрешимо, то <tex>B</tex> неразрешимо.
|proof=
Следует из второго свойства.
}}

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.

Например:
* [[Примеры неразрешимых задач: проблема соответствий Поста|неразрешимость проблемы соответствий Поста]].

==Сведение по Тьюрингу==
{{Определение
|definition=
Язык <tex>L</tex> '''сводится по Тьюрингу''' (является ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \leqslant_T M</tex>.
}}

{{Определение
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (''Turing equivalent'') языку <tex>M</tex>, если <tex>L \leqslant_T M</tex> и <tex>M \leqslant_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
}}

=== Свойства ===
* рефлексивность: <tex> L \leqslant_T L </tex>
* транзитивность: из <tex> L \leqslant_T M </tex> и <tex> M \leqslant_T N</tex> следует <tex> L \leqslant_T N </tex>
* Очевидно, что <tex>\equiv_T</tex> — отношение эквивалентности

=== Т-степени ===

Обозначим за <tex>\mathcal{D}_T</tex> множество классов эквивалентности языков по отношению <tex>\equiv_T</tex>, это множество будет множеством Т-степеней (тьюринговых степеней).

{{Определение
|definition=
Т-степенью языка <tex>L</tex> называется его класс эквивалентности по отношению <tex>\equiv_T</tex>, то есть <tex>\mathrm{deg}_T(L) = \{ M \mid L \equiv_T M \}</tex>.
}}

На Т-степенях можно ввести частичный порядок: для <tex>d_1, d_2 \in \mathcal{D}_T, d_1 \le d_2</tex>, если для каких-то <tex>L \in d_1, M \in d_2: L \leqslant_T M</tex>, определение корректно, так как порядок не будет зависеть от выбора представителя Т-степени.

==== Свойства ====
* <tex>\mathrm{R}</tex> — минимальный элемент в частичном порядке на Т-степенях. Очевидно из того, что класс разрешимых языков замкнут по использованию разрешимого языка в качестве оракула.
* Любая пара Т-степеней <tex>d_1, d_2 \in \mathcal{D}_T</tex> имеет наименьшую верхнюю границу <tex>d_1 \lor d_2 \in \mathcal{D}_T</tex>.

==== Тьюринговый скачок ====
Обозначим за <tex>H</tex> язык программ, останавливающихся на пустом входе. Обозначим за <tex>H^f</tex> язык программ, использующих <tex>f</tex> в качестве оракула и останавливающихся на пустом входе.

Можно показать, что:

* <tex>f <_T H^f</tex>
* Если <tex>f \le_T g</tex>, то <tex>H^f \le_T H^g</tex>

Тогда тьюринговым скачком Т-степени <tex>d</tex> называется Т-степень языка <tex>H^L</tex>, где <tex>L</tex> — произвольный язык в <tex>d</tex>. Заметим, что если <tex>L \equiv_T M</tex>, то <tex>H^L \equiv_T H^M</tex>, поэтому определение корректно. Оператор тьюрингова скачка обозначим как <tex>J : \mathcal{D}_T \to \mathcal{D}_T</tex>.

== Литература ==
* [http://en.wikipedia.org/wiki/Many-one_reduction Wikipedia — Many-one reduction]
* [http://en.wikipedia.org/wiki/Turing_reduction Wikipedia — Turing reduction]
* [http://www.personal.psu.edu/t20/notes/topics-s05.pdf Topics in Logic and Foundations]
* ''Верещагин Н., Шень А.'' — '''Вычислимые функции''', 2-е изд. МЦНМО, 2002, стр. 64. ISBN 5-900916-36-7
* ''P. Odifreddi'' — '''Classical recursion theory'''. Elsivier, 1992. ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}

Регулярная аппроксимация КС-языков

2016-11-19T19:57:15Z

5.18.224.199: /* Псевдокод */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''' (англ. ''self-embeded''), если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''' (англ. ''recursive''), если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <tex> A,B \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называются '''взаимно рекурсивными''' (англ. ''mutual recursive''), если <tex> \exists \alpha_1,\beta_1,\alpha_2,\beta_2 \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha_1 B \beta_1 \land B \Rightarrow^* \alpha_2 A \beta_2</tex> .
}}

== Алгоритм преобразования грамматики в конечный автомат ==
{{Лемма
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
|proof = В качестве конструктивного доказательства, мы приведем алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике. Для желающих, приведем ссылку на [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21#v=onepage&q&f=false формальное доказательство].

}}
=== Идея алгоритма ===
Пусть, <tex> N^* </tex> множество рекурсивных терминалов из <tex> N </tex>.
Пусть, <tex> P = \{N_1,N_2,...,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </tex> дизъюнктных множеств взаимно рекурсивных терминалов,
<tex> N_1 \cup N_2 \cup ... \cup N_k = N^* \land \forall i N_i \neq \emptyset </tex>.
Введем функцию <tex> getTheTypeOfMutualRecursiveSet(N_i): P \rightarrow \{left, right, self, cycle\} </tex>:
'''function''' IsLeftType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]</tex>

'''function''' IsRightType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]</tex>

'''function''' getTheTypeOfMutualRecursiveSet (<tex>N_i</tex>):
'''if''' !IsLeftType(<tex>N_i</tex>) && IsRightType(<tex>N_i</tex>)
return left;
'''if''' IsLeftType(<tex>N_i</tex>) && !IsRightType(<tex>N_i</tex>)
return right;
'''if''' (IsLeftType(<tex>N_i</tex>) && IsRightType(<tex>N_i</tex>)
return self;
'''if''' !IsLeftType(<tex>N_i</tex>) && !IsRightType(<tex>N_i</tex>)
return cyclic;
Заметим, что <tex> \forall i </tex> <tex>getTheTypeOfMutualRecursiveSet(N_i) \neq self </tex>, т.к в противном случае грамматика будет самоприменима. 
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
# символ алфавит или <tex> \varepsilon </tex> {{---}} добавляем новое правило в автомат
# нерекурсивный нетерминал {{---}} запускаемся от всех правых частей правил, который терминал порождает
# рекурсивный нетерминал {{---}} в зависимости от типа рекурсивного нетерминала, продолжаем рекурсию (будет ясно из пседокода)

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.

<tex>\Delta</tex> {{---}} множество переходов ДКА.

<tex>T</tex> {{---}} множество допускающих состояний.
'''function''' createFA(G) // <tex> G = \langle N, \Sigma, P, S \rangle</tex> 
<tex>\mathtt{Q} \leftarrow \varnothing</tex>
<tex>\Delta \leftarrow \varnothing </tex>
s = createState
f = createState
<tex>F \leftarrow \{f\} </tex>
'''return''' makeFA (s,S,f)

'''function''' makeFA (q0,a,q1)
'''if''' a == <tex> \varepsilon </tex> || a <tex> \in \Sigma</tex> // пришли в лист дерева разбора
<tex> \Delta = \Delta \cup \{(q_0,a,q_1)\} </tex>
'''return'''
'''if''' a == <tex>X\beta</tex> '''where''' <tex> X \in (N \cup \Sigma) \land \beta \in (N \cup \Sigma)^* \land |\beta| > 0 </tex>
q = createState
makeFA (<tex>q_0,X,q_1</tex>)
makeFA (<tex>q, \beta, q_1 </tex>)
'''return'''
'''if''' '''exist''' <tex> N_i </tex> '''where''' <tex> a \in N_i </tex>
'''foreach''' b '''in''' <tex>N_i</tex>
<tex>q_b</tex> = createState
'''if getTheTypeOfMutualRecursiveSet'''(<tex> N_i </tex>) == '''left'''
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_0, X_1 \cdots X_m, q_C</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_a,\varepsilon,q_1)\} </tex>
'''else''' // рекурсивный нетерминал right или cyclic
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_C, X_1 \cdots X_m, q_1</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_0, \varepsilon ,q_a)\} </tex>
'''return'''
'''foreach''' p '''in''' <tex>P</tex> '''where''' p == <tex> a \rightarrow \beta </tex>
makeFA (<tex> q_0, \beta, q_1 </tex>)

== Аппроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой контекстно-свободной грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex> к регулярной грамматике. Для удобства будем считать, что грамматика представлена в [[Нормальная форма Хомского|НФХ]].
[[Файл:RTN_Automat.png|280px|thumb|right|Автоматы <tex>T_A,T_B</tex> для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
=== RTN аппроксимация ===
Построим, по данной грамматике аппроксимирующий ее конечный автомат.
[[Файл:RTN_Automat1.png|280px|thumb|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим в него два состояния <tex> q_A</tex> и <tex>q_{A^*}</tex>.
#Для каждого правила грамматике <tex> (A \rightarrow X_1 \cdots X_m ) \in P</tex>, введм новые состояния в автомат этого нетерминала <tex> q_0^A \cdots q_m^A</tex>, а также добавим новые правила перехода в <tex> \Delta</tex>: <tex> (q_A, \varepsilon, q_0),(q_0^A,X_1,q_1^A), \cdots,(q_{m-1}^A,X_m,q_m^A),(q_m^A,\varepsilon,q_{A^*})</tex>.
#Таким образом мы построили множество конечных автоматов <tex>T</tex> = <tex> \{ T_A \| A \in N\}</tex> для каждого нетерминала <tex>A</tex>. Теперь объединим все в один автомат. Объединим все состоянии автоматов из <tex>T</tex> в множество <tex>Q</tex>. Скопируем все переходы каждого автомата из <tex>T</tex> в <tex>\Delta</tex>. Далее для каждого перехода вида <tex>(q,A,p), A\in N</tex>, вместо него добавим два новых перехода: <tex> (q, \varepsilon, q_A),(q_A^{*}, \varepsilon, p) </tex>.

===MT аппроксимация ===
Построим по данной самоприменимой контекстно-свободной грамматике <tex> G </tex> регулярную грамматику <tex> G^*</tex>.
#Для каждого нетерминала <tex> A \in N </tex> из <tex>G</tex>, добавим нетерминалы <tex>A</tex> и <tex> A^*</tex> в <tex> G^* </tex>.
#Для каждого правила <tex> A \rightarrow {\alpha}_{0} B_1 {\alpha}_{1} B_2 {\alpha}_{2} \cdots B_m {\alpha}_{m}</tex>, где <tex> B_1, \cdots, B_m \in N \land {\alpha}_i \in \Sigma^*</tex>. Добавим в <tex> G^*</tex> нетерминалы <tex> B_1 \cdots B_m , B_1^* \cdots B_m^*</tex> и следуюшие правила: <tex> A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \vdots \\ B^*_m \rightarrow {\alpha}_m A^* </tex>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha B \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
 Исходная грамматика <tex> G </tex> генерирует язык: <tex> \{(ab)^n a^n | n > 0\}</tex>. Результирущая грамматика <tex> G^*</tex> генирирует регулярный язык: <tex> (ab)^+ a^*</tex>. 

=== Сравнение двух методов ===
Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой. 
Привлекателным свойством MT аппроксимации по сравнению с RTN, то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике <tex> G</tex>, добавляется не более одного нового нетерминала в <tex> G^*</tex> и размер результирующий грамматики максимум в <tex>2</tex> раза больше, чем размер исходной. Так как для RTN апроксимации грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex>, количество состаяний апроксимируещего автомата в худшем случаи может составлять <tex> O(|N|^2)</tex>, что может быть критично для аппроксимации больших грамматик. 
Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках.

== Источники ==
* [http://books.google.ru/books?id=gvVK07D4wwUC&pg=PA161&lpg=PA161 книга, где можно узнать много нового про аппроксимации]
* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Fwww.cs.ucsb.edu%2F~omer%2FDOWNLOADABLE%2Fcfg-reg09.pdf&ei=AQbcUrL_DIfi4wSx3IDYDg&usg=AFQjCNHsSWONr0_c2MDgvApwrhc81deY0w&sig2=_2iZj4Xexe6-p5Cyt-GEMg&bvm=bv.59568121,d.bGE Разобрано много примеров аппроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной аппроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Регулярная аппроксимация КС-языков

2016-11-19T19:24:47Z

5.18.224.199: /* Сравнение двух методов */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''' (англ. ''self-embeded''), если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''' (англ. ''recursive''), если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <tex> A,B \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называются '''взаимно рекурсивными''' (англ. ''mutual recursive''), если <tex> \exists \alpha_1,\beta_1,\alpha_2,\beta_2 \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha_1 B \beta_1 \land B \Rightarrow^* \alpha_2 A \beta_2</tex> .
}}

== Алгоритм преобразования грамматики в конечный автомат ==
{{Лемма
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
|proof = В качестве конструктивного доказательства, мы приведем алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике. Для желающих, приведем ссылку на [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21#v=onepage&q&f=false формальное доказательство].

}}
=== Идея алгоритма ===
Пусть, <tex> N^* </tex> множество рекурсивных терминалов из <tex> N </tex>.
Пусть, <tex> P = \{N_1,N_2,...,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </tex> дизъюнктных множеств взаимно рекурсивных терминалов,
<tex> N_1 \cup N_2 \cup ... \cup N_k = N^* \land \forall i N_i \neq \emptyset </tex>.
Введем функцию <tex> getTheTypeOfMutualRecursiveSet(N_i): P \rightarrow \{left, right, self, cycle\} </tex>:
'''function''' IsLeftType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]</tex>

'''function''' IsRightType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]</tex>

'''function''' getTheTypeOfMutualRecursiveSet (<tex>N_i</tex>):
'''if''' !IsLeftType(<tex>N_i</tex>) && IsRightType(<tex>N_i</tex>)
return left;
'''if''' IsLeftType(<tex>N_i</tex>) && !IsRightType(<tex>N_i</tex>)
return right;
'''if''' (IsLeftType(<tex>N_i</tex>) && IsRightType(<tex>N_i</tex>)
return self;
'''if''' !IsLeftType(<tex>N_i</tex>) && !IsRightType(<tex>N_i</tex>)
return cyclic;
Заметим, что <tex> \forall i </tex> <tex>getTheTypeOfMutualRecursiveSet(N_i) \neq self </tex>, т.к в противном случае грамматика будет самоприменима. 
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
# символ алфавит или <tex> \varepsilon </tex> {{---}} добавляем новое правило в автомат
# нерекурсивный нетерминал {{---}} запускаемся от всех правых частей правил, который терминал порождает
# рекурсивный нетерминал {{---}} в зависимости от типа рекурсивного нетерминала, продолжаем рекурсию (будет ясно из пседокода)

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>\Delta</tex> {{---}} множество переходов ДКА.
<tex>T</tex> {{---}} множество допускающих состояний.
'''function''' createFA(G) // <tex> G = \langle N, \Sigma, P, S \rangle</tex>
<tex>\mathtt{Q} \leftarrow \varnothing</tex>
<tex>\Delta \leftarrow \varnothing </tex>
s = createState
f = createState
<tex>F \leftarrow \{f\} </tex>
'''return''' makeFA (s,S,f)

'''function''' makeFA (q0,a,q1)
'''if''' a == <tex> \varepsilon </tex> || a <tex> \in \Sigma</tex> // пришли в лист дерева разбора
<tex> \Delta = \Delta \cup \{(q_0,a,q_1)\} </tex>
'''return'''
'''if''' a == <tex>X\beta</tex> '''where''' <tex> X \in (N \cup \Sigma) \land \beta \in (N \cup \Sigma)^* \land |\beta| > 0 </tex>
q = createState
makeFA (<tex>q_0,X,q_1</tex>)
makeFA (<tex>q, \beta, q_1 </tex>)
'''return'''
'''if''' '''exist''' <tex> N_i </tex> '''where''' <tex> a \in N_i </tex>
'''foreach''' b '''in''' <tex>N_i</tex>
<tex>q_b</tex> = createState
'''if getTheTypeOfMutualRecursiveSet'''(<tex> N_i </tex>) == '''left'''
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_0, X_1 \cdots X_m, q_C</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_a,\varepsilon,q_1)\} </tex>
'''else''' // рекурсивный нетерминал rihgt или cyclic
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_C, X_1 \cdots X_m, q_1</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_0, \varepsilon ,q_a)\} </tex>
'''return'''
'''foreach''' p '''in''' <tex>P</tex> '''where''' p == <tex> a \rightarrow \beta </tex>
makeFA (<tex> q_0, \beta, q_1 </tex>)

== Аппроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой контекстно-свободной грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex> к регулярной грамматике. Для удобства будем считать, что грамматика представлена в [[Нормальная форма Хомского|НФХ]].
[[Файл:RTN_Automat.png|280px|thumb|right|Автоматы <tex>T_A,T_B</tex> для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
=== RTN аппроксимация ===
Построим, по данной грамматике аппроксимирующий ее конечный автомат.
[[Файл:RTN_Automat1.png|280px|thumb|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим в него два состояния <tex> q_A</tex> и <tex>q_{A^*}</tex>.
#Для каждого правила грамматике <tex> (A \rightarrow X_1 \cdots X_m ) \in P</tex>, введм новые состояния в автомат этого нетерминала <tex> q_0^A \cdots q_m^A</tex>, а также добавим новые правила перехода в <tex> \Delta</tex>: <tex> (q_A, \varepsilon, q_0),(q_0^A,X_1,q_1^A), \cdots,(q_{m-1}^A,X_m,q_m^A),(q_m^A,\varepsilon,q_{A^*})</tex>.
#Таким образом мы построили множество конечных автоматов <tex>T</tex> = <tex> \{ T_A \| A \in N\}</tex> для каждого нетерминала <tex>A</tex>. Теперь объединим все в один автомат. Объединим все состоянии автоматов из <tex>T</tex> в множество <tex>Q</tex>. Скопируем все переходы каждого автомата из <tex>T</tex> в <tex>\Delta</tex>. Далее для каждого перехода вида <tex>(q,A,p), A\in N</tex>, вместо него добавим два новых перехода: <tex> (q, \varepsilon, q_A),(q_A^{*}, \varepsilon, p) </tex>.

===MT аппроксимация ===
Построим по данной самоприменимой контекстно-свободной грамматике <tex> G </tex> регулярную грамматику <tex> G^*</tex>.
#Для каждого нетерминала <tex> A \in N </tex> из <tex>G</tex>, добавим нетерминалы <tex>A</tex> и <tex> A^*</tex> в <tex> G^* </tex>.
#Для каждого правила <tex> A \rightarrow {\alpha}_{0} B_1 {\alpha}_{1} B_2 {\alpha}_{2} \cdots B_m {\alpha}_{m}</tex>, где <tex> B_1, \cdots, B_m \in N \land {\alpha}_i \in \Sigma^*</tex>. Добавим в <tex> G^*</tex> нетерминалы <tex> B_1 \cdots B_m , B_1^* \cdots B_m^*</tex> и следуюшие правила: <tex> A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \vdots \\ B^*_m \rightarrow {\alpha}_m A^* </tex>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha B \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
 Исходная грамматика <tex> G </tex> генерирует язык: <tex> \{(ab)^n a^n | n > 0\}</tex>. Результирущая грамматика <tex> G^*</tex> генирирует регулярный язык: <tex> (ab)^+ a^*</tex>. 

=== Сравнение двух методов ===
Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой. 
Привлекателным свойством MT аппроксимации по сравнению с RTN, то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике <tex> G</tex>, добавляется не более одного нового нетерминала в <tex> G^*</tex> и размер результирующий грамматики максимум в <tex>2</tex> раза больше, чем размер исходной. Так как для RTN апроксимации грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex>, количество состаяний апроксимируещего автомата в худшем случаи может составлять <tex> O(|N|^2)</tex>, что может быть критично для аппроксимации больших грамматик. 
Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках.

== Источники ==
* [http://books.google.ru/books?id=gvVK07D4wwUC&pg=PA161&lpg=PA161 книга, где можно узнать много нового про аппроксимации]
* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Fwww.cs.ucsb.edu%2F~omer%2FDOWNLOADABLE%2Fcfg-reg09.pdf&ei=AQbcUrL_DIfi4wSx3IDYDg&usg=AFQjCNHsSWONr0_c2MDgvApwrhc81deY0w&sig2=_2iZj4Xexe6-p5Cyt-GEMg&bvm=bv.59568121,d.bGE Разобрано много примеров аппроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной аппроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Регулярная аппроксимация КС-языков

2016-11-19T19:19:17Z

5.18.224.199: /* MT аппроксимация */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''' (англ. ''self-embeded''), если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''' (англ. ''recursive''), если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <tex> A,B \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называются '''взаимно рекурсивными''' (англ. ''mutual recursive''), если <tex> \exists \alpha_1,\beta_1,\alpha_2,\beta_2 \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha_1 B \beta_1 \land B \Rightarrow^* \alpha_2 A \beta_2</tex> .
}}

== Алгоритм преобразования грамматики в конечный автомат ==
{{Лемма
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
|proof = В качестве конструктивного доказательства, мы приведем алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике. Для желающих, приведем ссылку на [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21#v=onepage&q&f=false формальное доказательство].

}}
=== Идея алгоритма ===
Пусть, <tex> N^* </tex> множество рекурсивных терминалов из <tex> N </tex>.
Пусть, <tex> P = \{N_1,N_2,...,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </tex> дизъюнктных множеств взаимно рекурсивных терминалов,
<tex> N_1 \cup N_2 \cup ... \cup N_k = N^* \land \forall i N_i \neq \emptyset </tex>.
Введем функцию <tex> getTheTypeOfMutualRecursiveSet(N_i): P \rightarrow \{left, right, self, cycle\} </tex>:
'''function''' IsLeftType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]</tex>

'''function''' IsRightType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]</tex>

'''function''' getTheTypeOfMutualRecursiveSet (<tex>N_i</tex>):
'''if''' !IsLeftType(<tex>N_i</tex>) && IsRightType(<tex>N_i</tex>)
return left;
'''if''' IsLeftType(<tex>N_i</tex>) && !IsRightType(<tex>N_i</tex>)
return right;
'''if''' (IsLeftType(<tex>N_i</tex>) && IsRightType(<tex>N_i</tex>)
return self;
'''if''' !IsLeftType(<tex>N_i</tex>) && !IsRightType(<tex>N_i</tex>)
return cyclic;
Заметим, что <tex> \forall i </tex> <tex>getTheTypeOfMutualRecursiveSet(N_i) \neq self </tex>, т.к в противном случае грамматика будет самоприменима. 
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
# символ алфавит или <tex> \varepsilon </tex> {{---}} добавляем новое правило в автомат
# нерекурсивный нетерминал {{---}} запускаемся от всех правых частей правил, который терминал порождает
# рекурсивный нетерминал {{---}} в зависимости от типа рекурсивного нетерминала, продолжаем рекурсию (будет ясно из пседокода)

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>\Delta</tex> {{---}} множество переходов ДКА.
<tex>T</tex> {{---}} множество допускающих состояний.
'''function''' createFA(G) // <tex> G = \langle N, \Sigma, P, S \rangle</tex>
<tex>\mathtt{Q} \leftarrow \varnothing</tex>
<tex>\Delta \leftarrow \varnothing </tex>
s = createState
f = createState
<tex>F \leftarrow \{f\} </tex>
'''return''' makeFA (s,S,f)

'''function''' makeFA (q0,a,q1)
'''if''' a == <tex> \varepsilon </tex> || a <tex> \in \Sigma</tex> // пришли в лист дерева разбора
<tex> \Delta = \Delta \cup \{(q_0,a,q_1)\} </tex>
'''return'''
'''if''' a == <tex>X\beta</tex> '''where''' <tex> X \in (N \cup \Sigma) \land \beta \in (N \cup \Sigma)^* \land |\beta| > 0 </tex>
q = createState
makeFA (<tex>q_0,X,q_1</tex>)
makeFA (<tex>q, \beta, q_1 </tex>)
'''return'''
'''if''' '''exist''' <tex> N_i </tex> '''where''' <tex> a \in N_i </tex>
'''foreach''' b '''in''' <tex>N_i</tex>
<tex>q_b</tex> = createState
'''if getTheTypeOfMutualRecursiveSet'''(<tex> N_i </tex>) == '''left'''
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_0, X_1 \cdots X_m, q_C</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_a,\varepsilon,q_1)\} </tex>
'''else''' // рекурсивный нетерминал rihgt или cyclic
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_C, X_1 \cdots X_m, q_1</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_0, \varepsilon ,q_a)\} </tex>
'''return'''
'''foreach''' p '''in''' <tex>P</tex> '''where''' p == <tex> a \rightarrow \beta </tex>
makeFA (<tex> q_0, \beta, q_1 </tex>)

== Аппроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой контекстно-свободной грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex> к регулярной грамматике. Для удобства будем считать, что грамматика представлена в [[Нормальная форма Хомского|НФХ]].
[[Файл:RTN_Automat.png|280px|thumb|right|Автоматы <tex>T_A,T_B</tex> для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
=== RTN аппроксимация ===
Построим, по данной грамматике аппроксимирующий ее конечный автомат.
[[Файл:RTN_Automat1.png|280px|thumb|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим в него два состояния <tex> q_A</tex> и <tex>q_{A^*}</tex>.
#Для каждого правила грамматике <tex> (A \rightarrow X_1 \cdots X_m ) \in P</tex>, введм новые состояния в автомат этого нетерминала <tex> q_0^A \cdots q_m^A</tex>, а также добавим новые правила перехода в <tex> \Delta</tex>: <tex> (q_A, \varepsilon, q_0),(q_0^A,X_1,q_1^A), \cdots,(q_{m-1}^A,X_m,q_m^A),(q_m^A,\varepsilon,q_{A^*})</tex>.
#Таким образом мы построили множество конечных автоматов <tex>T</tex> = <tex> \{ T_A \| A \in N\}</tex> для каждого нетерминала <tex>A</tex>. Теперь объединим все в один автомат. Объединим все состоянии автоматов из <tex>T</tex> в множество <tex>Q</tex>. Скопируем все переходы каждого автомата из <tex>T</tex> в <tex>\Delta</tex>. Далее для каждого перехода вида <tex>(q,A,p), A\in N</tex>, вместо него добавим два новых перехода: <tex> (q, \varepsilon, q_A),(q_A^{*}, \varepsilon, p) </tex>.

===MT аппроксимация ===
Построим по данной самоприменимой контекстно-свободной грамматике <tex> G </tex> регулярную грамматику <tex> G^*</tex>.
#Для каждого нетерминала <tex> A \in N </tex> из <tex>G</tex>, добавим нетерминалы <tex>A</tex> и <tex> A^*</tex> в <tex> G^* </tex>.
#Для каждого правила <tex> A \rightarrow {\alpha}_{0} B_1 {\alpha}_{1} B_2 {\alpha}_{2} \cdots B_m {\alpha}_{m}</tex>, где <tex> B_1, \cdots, B_m \in N \land {\alpha}_i \in \Sigma^*</tex>. Добавим в <tex> G^*</tex> нетерминалы <tex> B_1 \cdots B_m , B_1^* \cdots B_m^*</tex> и следуюшие правила: <tex> A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \vdots \\ B^*_m \rightarrow {\alpha}_m A^* </tex>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha B \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
 Исходная грамматика <tex> G </tex> генерирует язык: <tex> \{(ab)^n a^n | n > 0\}</tex>. Результирущая грамматика <tex> G^*</tex> генирирует регулярный язык: <tex> (ab)^+ a^*</tex>. 

=== Сравнение двух методов ===
Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой. 
Привлекателным свойством MT аппроксимации по сравнению с RTN, то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике <tex> G</tex>, добавляется не более одного нового нетерминала в <tex> G^*</tex> и размер результирующий грамматики максимум в 2 раза больше, чем размер исходной. Так как для RTN апроксимации грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex>, количество состаяний апроксимируещего автомата в худшем случаи может составлять <tex> O(|N|^2)</tex>, что может быть критично для аппроксимации больших грамматик. 
Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках.

== Источники ==
* [http://books.google.ru/books?id=gvVK07D4wwUC&pg=PA161&lpg=PA161 книга, где можно узнать много нового про аппроксимации]
* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Fwww.cs.ucsb.edu%2F~omer%2FDOWNLOADABLE%2Fcfg-reg09.pdf&ei=AQbcUrL_DIfi4wSx3IDYDg&usg=AFQjCNHsSWONr0_c2MDgvApwrhc81deY0w&sig2=_2iZj4Xexe6-p5Cyt-GEMg&bvm=bv.59568121,d.bGE Разобрано много примеров аппроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной аппроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Регулярная аппроксимация КС-языков

2016-11-19T19:18:06Z

5.18.224.199: /* Аппроксимации самоприменимой грамматики */

==Определения==
{{Определение
|definition =
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная]] грамматика <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''самоприменимой''' (англ. ''self-embeded''), если <tex> \exists A \in N: A \Rightarrow^* \alpha A \beta</tex>, <tex> \alpha \neq \varepsilon \land \beta \neq \varepsilon </tex> .
}}
{{Определение
|definition =
Нетерминал <tex> A \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называется '''рекурсивным''' (англ. ''recursive''), если <tex> \exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta</tex> .
}}
{{Определение
|definition =
Нетерминалы <tex> A,B \in N</tex> в грамматике <tex> G = \langle N, \Sigma, P, S \rangle</tex> называются '''взаимно рекурсивными''' (англ. ''mutual recursive''), если <tex> \exists \alpha_1,\beta_1,\alpha_2,\beta_2 \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha_1 B \beta_1 \land B \Rightarrow^* \alpha_2 A \beta_2</tex> .
}}

== Алгоритм преобразования грамматики в конечный автомат ==
{{Лемма
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
|proof = В качестве конструктивного доказательства, мы приведем алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике. Для желающих, приведем ссылку на [http://books.google.ru/books?id=tFvtwGYNe7kC&pg=PA21#v=onepage&q&f=false формальное доказательство].

}}
=== Идея алгоритма ===
Пусть, <tex> N^* </tex> множество рекурсивных терминалов из <tex> N </tex>.
Пусть, <tex> P = \{N_1,N_2,...,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </tex> дизъюнктных множеств взаимно рекурсивных терминалов,
<tex> N_1 \cup N_2 \cup ... \cup N_k = N^* \land \forall i N_i \neq \emptyset </tex>.
Введем функцию <tex> getTheTypeOfMutualRecursiveSet(N_i): P \rightarrow \{left, right, self, cycle\} </tex>:
'''function''' IsLeftType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]</tex>

'''function''' IsRightType(<tex>N_i</tex>)
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]</tex>

'''function''' getTheTypeOfMutualRecursiveSet (<tex>N_i</tex>):
'''if''' !IsLeftType(<tex>N_i</tex>) && IsRightType(<tex>N_i</tex>)
return left;
'''if''' IsLeftType(<tex>N_i</tex>) && !IsRightType(<tex>N_i</tex>)
return right;
'''if''' (IsLeftType(<tex>N_i</tex>) && IsRightType(<tex>N_i</tex>)
return self;
'''if''' !IsLeftType(<tex>N_i</tex>) && !IsRightType(<tex>N_i</tex>)
return cyclic;
Заметим, что <tex> \forall i </tex> <tex>getTheTypeOfMutualRecursiveSet(N_i) \neq self </tex>, т.к в противном случае грамматика будет самоприменима. 
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
# символ алфавит или <tex> \varepsilon </tex> {{---}} добавляем новое правило в автомат
# нерекурсивный нетерминал {{---}} запускаемся от всех правых частей правил, который терминал порождает
# рекурсивный нетерминал {{---}} в зависимости от типа рекурсивного нетерминала, продолжаем рекурсию (будет ясно из пседокода)

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>\Delta</tex> {{---}} множество переходов ДКА.
<tex>T</tex> {{---}} множество допускающих состояний.
'''function''' createFA(G) // <tex> G = \langle N, \Sigma, P, S \rangle</tex>
<tex>\mathtt{Q} \leftarrow \varnothing</tex>
<tex>\Delta \leftarrow \varnothing </tex>
s = createState
f = createState
<tex>F \leftarrow \{f\} </tex>
'''return''' makeFA (s,S,f)

'''function''' makeFA (q0,a,q1)
'''if''' a == <tex> \varepsilon </tex> || a <tex> \in \Sigma</tex> // пришли в лист дерева разбора
<tex> \Delta = \Delta \cup \{(q_0,a,q_1)\} </tex>
'''return'''
'''if''' a == <tex>X\beta</tex> '''where''' <tex> X \in (N \cup \Sigma) \land \beta \in (N \cup \Sigma)^* \land |\beta| > 0 </tex>
q = createState
makeFA (<tex>q_0,X,q_1</tex>)
makeFA (<tex>q, \beta, q_1 </tex>)
'''return'''
'''if''' '''exist''' <tex> N_i </tex> '''where''' <tex> a \in N_i </tex>
'''foreach''' b '''in''' <tex>N_i</tex>
<tex>q_b</tex> = createState
'''if getTheTypeOfMutualRecursiveSet'''(<tex> N_i </tex>) == '''left'''
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_0, X_1 \cdots X_m, q_C</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_a,\varepsilon,q_1)\} </tex>
'''else''' // рекурсивный нетерминал rihgt или cyclic
'''foreach''' C '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow X_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_C, X_1 \cdots X_m, q_1</tex>)
'''foreach''' C,D '''in''' <tex>N_i</tex> '''where''' <tex> C \rightarrow DX_1...X_m \land X_1,...X_m \neq N_i </tex>
makeFA (<tex>q_D, X_1 \cdots X_m, q_C</tex>)
<tex> \Delta = \Delta \cup \{(q_0, \varepsilon ,q_a)\} </tex>
'''return'''
'''foreach''' p '''in''' <tex>P</tex> '''where''' p == <tex> a \rightarrow \beta </tex>
makeFA (<tex> q_0, \beta, q_1 </tex>)

== Аппроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой контекстно-свободной грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex> к регулярной грамматике. Для удобства будем считать, что грамматика представлена в [[Нормальная форма Хомского|НФХ]].
[[Файл:RTN_Automat.png|280px|thumb|right|Автоматы <tex>T_A,T_B</tex> для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
=== RTN аппроксимация ===
Построим, по данной грамматике аппроксимирующий ее конечный автомат.
[[Файл:RTN_Automat1.png|280px|thumb|left|Конечный автомат для грамматики
<tex>A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f </tex>]]
#Для каждого нетерминала <tex> A</tex> в грамматике, создадим новый конечный автомат <tex> T_A</tex>, добавим в него два состояния <tex> q_A</tex> и <tex>q_{A^*}</tex>.
#Для каждого правила грамматике <tex> (A \rightarrow X_1 \cdots X_m ) \in P</tex>, введм новые состояния в автомат этого нетерминала <tex> q_0^A \cdots q_m^A</tex>, а также добавим новые правила перехода в <tex> \Delta</tex>: <tex> (q_A, \varepsilon, q_0),(q_0^A,X_1,q_1^A), \cdots,(q_{m-1}^A,X_m,q_m^A),(q_m^A,\varepsilon,q_{A^*})</tex>.
#Таким образом мы построили множество конечных автоматов <tex>T</tex> = <tex> \{ T_A \| A \in N\}</tex> для каждого нетерминала <tex>A</tex>. Теперь объединим все в один автомат. Объединим все состоянии автоматов из <tex>T</tex> в множество <tex>Q</tex>. Скопируем все переходы каждого автомата из <tex>T</tex> в <tex>\Delta</tex>. Далее для каждого перехода вида <tex>(q,A,p), A\in N</tex>, вместо него добавим два новых перехода: <tex> (q, \varepsilon, q_A),(q_A^{*}, \varepsilon, p) </tex>.

===MT аппроксимация ===
Построим, по данной самоприменимой кс грамматике <tex> G </tex>, регулярную грамматику <tex> G^*</tex>.
#Для каждого нетерминала <tex> A \in N </tex> из <tex>G</tex>, добавим нетерминалы <tex>A</tex> и <tex> A^*</tex> в <tex> G^* </tex>.
#Для каждого правила <tex> A \rightarrow {\alpha}_{0} B_1 {\alpha}_{1} B_2 {\alpha}_{2} \cdots B_m {\alpha}_{m}</tex>, где <tex> B_1, \cdots, B_m \in N \land {\alpha}_i \in \Sigma^*</tex>. Добавим в <tex> G^*</tex> нетерминалы <tex> B_1 \cdots B_m , B_1^* \cdots B_m^*</tex> и следуюшие правила: <tex> A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \vdots \\ B^*_m \rightarrow {\alpha}_m A^* </tex>. (Если <tex>m = 0 </tex>, тогда добавим правило <tex> A \rightarrow {\alpha}_0 A^* </tex>).
В итоге <tex> G^*</tex> {{---}} [[Правоконтекстные грамматики, эквивалентность автоматам|правоконтекстная грамматика]], эквивалентная конечному автомату, который задает регулярный язык.
==== Пример ====
<tex> G = \left\{\begin{matrix} A \rightarrow \alpha B \alpha
\\ B \rightarrow \beta A | \beta
\end{matrix}\right.\Rightarrow G^* = \left\{\begin{matrix} A \rightarrow \alpha B
\\ A^* \rightarrow B^* | \varepsilon
\\ B \rightarrow \beta A | \beta B^*
\\ B^* \rightarrow \alpha A^* | \varepsilon
\end{matrix}\right.</tex>
 Исходная грамматика <tex> G </tex> генерирует язык: <tex> \{(ab)^n a^n | n > 0\}</tex>. Результирущая грамматика <tex> G^*</tex> генирирует регулярный язык: <tex> (ab)^+ a^*</tex>. 
=== Сравнение двух методов ===
Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой. 
Привлекателным свойством MT аппроксимации по сравнению с RTN, то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике <tex> G</tex>, добавляется не более одного нового нетерминала в <tex> G^*</tex> и размер результирующий грамматики максимум в 2 раза больше, чем размер исходной. Так как для RTN апроксимации грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex>, количество состаяний апроксимируещего автомата в худшем случаи может составлять <tex> O(|N|^2)</tex>, что может быть критично для аппроксимации больших грамматик. 
Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках.

== Источники ==
* [http://books.google.ru/books?id=gvVK07D4wwUC&pg=PA161&lpg=PA161 книга, где можно узнать много нового про аппроксимации]
* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Fwww.cs.ucsb.edu%2F~omer%2FDOWNLOADABLE%2Fcfg-reg09.pdf&ei=AQbcUrL_DIfi4wSx3IDYDg&usg=AFQjCNHsSWONr0_c2MDgvApwrhc81deY0w&sig2=_2iZj4Xexe6-p5Cyt-GEMg&bvm=bv.59568121,d.bGE Разобрано много примеров аппроксимаций]

* [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Facl.ldc.upenn.edu%2FJ%2FJ00%2FJ00-1003.pdf&ei=CgfcUrWwA-mF4ATY7IHQAQ&usg=AFQjCNG3QHL7yQSwTUbSi9xkse2j0p6YaA&sig2=UF88aXWRAbapv4o_UrIjGg&bvm=bv.59568121,d.bGE практические эксперименты с регулярной аппроксимацией]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]