Грамматики

Итак, мы переходим к определению порождающих грамматик в смысле Н.Хомского; до тех пор, пока не будут введены в рассмотрение другие типы грамматик, - а по большей части и после этого (когда невозможно недоразумение) – мы будем в качестве синонима для выражения «порождающая грамматика» употреблять просто слово «грамматика».

(Порождающая) грамматика – это упорядоченная четвёрка Г = á V, W, I, R ñ, где: 1) V и 2) W - непересекающиеся непустые конечные множества; 3) I - некоторый элемент W; 4) R - конечное множество цепочек вида φ → ψ, где φ и ψ - различные цепочки в словаре V U W и → - символ, не входящий в V U W. Множества V и W называются соответственно основным и вспомогательным словарями (алфавитами) грамматики Г, а их элементы – соответственно основными и вспомогательными символами и Г**); I называется начальным символом Г, R - схемой Г и элементы R - правилами Г. Цепочки φ и ψ называются соответственно левой и правой частями правила φ → ψ. Объединение V U W мы будем иногда называть полным словарём грамматики Г.

Пусть r = φ → ψ – правило грамматики Г и ξ_{1 *} φ _* ξ₂ – вхождение φ в цепочку ω = ξ₁φξ₂ в словаре V U W. В этом случае мы будем говорить, что цепочка h = ξ₁ψξ₂ получается из w применением правила r к вхождению ξ_{1 *} φ _* ξ₂ цепочки φ. Если цепочка h получается из цепочки ω применением какого-либо правила Г, будем говорить, что h непосредственно выводима из ω в Г, и писать ω|=_Гh или просто ω|=h.

Последовательность цепочек D = (ω₀, ω₁,…, ω_n) (n ≥1) называется выводом ω_n из ω₀ в грамматике Г, если для каждого i, 1 ≤ i ≤ n, имеет место ω _{i -1} = ω _i. Число n называется длиной вывода D. Если существует вывод h из ω в Г, то мы будем говорить, что h выводима из ω в Г, и писать ω| – _Гh или ω| – h.

Вывод (ω₀, ω₁,…, ω_n) называется полным, если ω₀ = I и ω_n – цепочка в словаре V.

Если D = (ω₀, ω₁,…, ω_n) – вывод в грамматике Г и для некоторого I = 1, …, n цепочка ω _i получается из ω _{i -1} применением правила φ → ψ к вхождению = ξ _{i *}ψ_*h _i цепочки φ в ω _{i -1}, то мы будем говорить, что это правило применяется на i-м шаге вывода D к вхождению ξ _{i *}ψ_*h _i и что данное вхождение φ в ω заменяется на i-м шаге вывода D. Размеченным выводом, соответствующим выводу D, мы будем называть последовательность (ω^∕₀, ω^∕₁,…, ω^∕_n-1, ω_n), где ω^∕ _i (i = 0, …, n – 1) – вхождение, заменяемое на i -м шаге вывода D. Одному выводу может, вообще говоря, соответствовать много размеченных выводов (см. упражнение 1.9.).

Множество цепочек в основном словаре грамматики Г, выводимых из её начального символа (иначе – множество последних цепочек всевозможных полных выводов в Г), называется языком, порождаемым грамматикой Г, и обозначается L (Г).

Из сформулированных определений видно, что существенным свойством процесса работы порождающей грамматики является его недетерминированность: если оборвать вывод на каком-либо шаге, то продолжение, вообще говоря, не восстанавливается однозначно по оставшейся части и может быть выполнено разными способами. Таким образом, грамматика – это исчисление, т.е. разрешение производить некоторые операции [Марков 1954, стр. 203] – в данном случае подстановки в цепочки одних подцепочек вместо других (а не алгоритм, т.е. не предписание производить какие-то операции).

Пример. Пусть Г = á{ a, b, c }, { A, B, C, D }, A, { A → BCA, BCB → D, BC → bc, DC → a, cA → c, aA → a }ñ. Пример полного вывода в Г: (А, ВСА, ВСВСА, ВСВСВСА, ВСDСА, ВСDСВСА, ВСDСbсА, ВСаbсА, bсаbсА, bсаbс). Соответствующий размеченный вывод (в данном случае единственный): (* А *, ВС * А *, ВСВС * А *, ВС * ВСВ * СА, ВСDС * А *, ВСDС * ВС * А, ВС * DС * bсА, * ВС * аbсА, bсаb * сА *, bсаbс). Легко видеть, что L (Г) = { a, bc }+.

Грамматика Г = á V, W, I, R ñ называется грамматикой составляющих, или НС-грамматикой *), если каждое её правило имеет вид ξ₁ А ξ₂ → ξ₁θξ₂, где ξ₁, ξ₂ - произвольные цепочки в словаре V U W, А Î W и θ - произвольная непустая цепочка в V U W.

Правила вида ξ₁ А ξ₂ → ξ₁θξ₂, где ξ₁, ξ₂, А и θ имеют указанный только что смысл, иногда называют НС-правилами; цепочка ξ₁, цепочка ξ₂ и пара цепочек (ξ₁,ξ₂) называются соответственно левым контекстом, правым контекстом и контекстом НС-правила ξ₁ А ξ₂ → ξ₁θξ₂. При применении НС-правила фактически заменяется только одно вхождение символа А. но возможность замены зависит от наличия нужного контекста. Если ξ₁ = ξ₂ = L, то правило называется бесконтекстным (или контекстно-свободным), сокращенно Б-правилом (или КС-правилом).

НС-грамматика называется бесконтекстной (или контекстно-свободной), сокращенно Б-грамматикой (или КС-грамматикой), если все её правила бесконтекстные.

(Б-) грамматика называется автоматной, сокращенно А-грамматикой ^**), если каждое её правило имеет вид А → аВ или А → а, где А, В – вспомогательные символы и а основной символ.

Языки, порождаемые НС-, Б- и А-грамматиками, называются соответственно НС-, Б- и А-языками.

ЛИТЕРАТУРА

Автоматизированные информационные системы. Криницкий Н.А., Миронов Г. А., Флоров Г. Д./ Под ред. А.А.Дородницына. – М.: Наука. Главная редакция физико-математической литературы, 1982.-384 с.

11. Елементи теорії алгоритмів. Машина Тьюринга. (2 год.)

МАШИНА ТЬЮРИНГА

Вопрос: можно ли уточнить непосредственно само понятие алгоритма, а затем с его помощью определить и класс вычислимых функций?

Это было сделано в 1936-37 гг. Постом и Тьюрингом независимо друг от друга.

Основная мысль Поста и Тьюринга заключалась в том, что алгоритмические процессы - это процессы, которые может совершать подходяще устроенная "машина". В соответствии с этим ими с помощью точных математических терминов были описаны довольно узкие классы машин. На этих машинах оказалось возможным осуществить или имитировать все алгоритмические процессы, которые фактически когда-либо описывались математиками.

Машины, введенные Постом и Тьюрингом, отличались не очень существенно, и в дальнейшем стали называться машинами Тьюринга.

Под машинами Поста и Тьюринга понимается некоторая гипотетическая (условная) машина, состоящая из следующих частей:

информационной ленты, представляющей собой бесконечную (неограниченную) память машины, разделенную на отдельные ячейки. В каждой ячейке можно поместить лишь один символ, в том числе и нуль;

"считывающей головки" - специального чувствительного элемента, способного обозревать содержимое ячеек. Вдоль головки информационная лента перемещается в обе стороны так, чтобы в каждый рассматриваемый момент времени головка находилась в одной определенной ячейке ленты;

управляющего устройства, которое в каждый рассматриваемый момент находится в некотором "состоянии". Предполагается, что устройство управления машины может находиться в некотором конечном числе состояний. Состояние устройства управления часто называют внутренним состоянием машины. Одно из этих состояний называется заключительным и в работе машины играет особую роль, так как оно управляет окончанием работы машины.

Схематически машина представлена на рис.1.

q

j

Рис. 1.

В алгоритмической системе Поста информация представляется в двоичном алфавите.

Таким образом, в каждой ячейке информационной ленты можно поместить либо 0, либо 1. Алгоритм представляется в виде конечного упорядоченного набора правил, называемых приказами. Работа алгоритма начинается с некоторой начальной ячейки, соответствующей первому приказу алгоритма. Составляющие алгоритм приказы могут принадлежать к одному из 6, выполняемых машиной Поста:

1. Записать в рассматриваемую ячейку 1 и перейти к j - тому приказу.

2. Записать в рассматриваемую ячейку 0 и перейти к i - тому приказу.

3. Сдвинуть ленту вправо на одну ячейку и приступить к выполнению i - того приказа.

4. Сдвинуть ленту влево на одну ячейку и приступить к выполнению i - того приказа.

5. Если в рассматриваемой ячейке записана 1, то перейти к выполнению j -того приказа, а если записан 0, то перейти к выполнению i - того приказа.

6. Окончание работы алгоритма, остановка.

Таким образом, алгоритмическая машина Поста представляет собой машину с информационной лентой, содержащей в каждой ячейке либо 0, либо1; с лентой, перемещающейся влево и вправо вдоль головки; с устройством управления, выполняющим 6 приказов (с внутренними состояниями).

Алгоритмы, составленные из любого конечного числа правил, представленных приказами машины Поста, называются алгоритмами Поста. Доказано, что алгоритмы Поста сводятся к алгоритмам, реализуемым с помощью частично рекурсивных функций, и наоборот, любая частично рекурсивная функция может быть представлена алгоритмом системы Поста..

В отличие от машины Поста в каждой ячейке машины Тьюринга может находиться один из символов некоторого конечного алфавита, а устройство управления может быть в одном из конечных состояний. Другими словами, машина Тьюринга, работая в произвольном конечном алфавите, может выполнять некоторое конечное количество приказов. При этом машины Тьюринга, как и машины Поста, могут сдвигать ленту на одну ячейку вправо или влево, оставляя содержимое ячеек неизменным, или могут заменять состояние воспринимаемой ячейки, оставляя ленту неподвижной.

Пусть алфавит машины Тьюринга задан в виде множества А = { s₀ , s_i,... s_n }, где s₀ соответствует пустой ячейке, а число состояний устройства задано в виде множества

Q = { q₀ , q_i,... q_m }, где q₀ соответствует заключительному состоянию.

Конечная совокупность символов алфавита, с которой работает машина, называется внешним алфавитом, конечная совокупность состояний устройства управления - внутренним алфавитом.

Совокупность, образованная последовательностью состояний всех ячеек ленты и состоянием устройства управления, называется конфигурацией машины. Конфигурация задается в виде слова, описывающего конкретное состояние машины.

Если машина Тьюринга, находясь в состоянии q_i, и воспринимая записанный на ленте символ s_k, переходит в новое состояние q_j, осуществляя при этом замену символа в рассматриваемой ячейке на символ s_m и сдвиг ленты на одну ячейку, то говорят, что машина выполняет команду q_i s_k ® q_j s_mЛ. Если замены не происходит, s_m может в команде отсутствовать.

При манипуляциях с лентой принимаются следующие обозначения:[16]

Л - движение ленты влево;

П - движение ленты вправо;

С - нет движения ленты (стоп).

Рассмотрим пример машины Тьюринга с алфавитами А = {0,1}, Q = { q_0, q₁ } и командами:

q₁1q₁1Л,

q₁0, q₀1С.

Пусть на ленте имеется слово 11100. Головка расположена над первой слева единицей. В результате работы машины Тьюринга это слово превращается в 11110. По окончании работы машины головка стоит над крайней правой единицей.

Совокупность всех команд, которые может выполнять машина, называется ее программой.

Будем считать машину Тьюринга заданной, если заданы ее внешний и внутренний алфавиты, программа, начальная конфигурация и указано, какие из символов обозначают пустую ячейку и заключительное состояние.

Пусть машина Тьюринга задана внешним алфавитом А = { s₀ , a, b, c, d } и внутренним алфавитом Q = { q₀ , q₁, q₂ , q₃, q₄, q₅ }, и совокупностью команд

q₀ a q₁ aЛ, q₀ b q₀ bЛ, q₂ a q₅ dП, q₀ c q₀ cЛ, q₁ d q₂ cП, q₃ a q₄ dП, q₄ b q₂ cП.

Пустую ячейку обозначает символ s₀, а заключительное состояние - q₅.

Рапссмотри применение данной машины Тьюринга для переработки исходного слова bcadc, которое даст нам слово bcdcc. Начальная конфигурация имеет вид q₀bcadc, при этоммашиной будет порождена следующая последовательность конфигураций:

1 шаг bq₀cadc, результат выполнения команды (q₀ b ® q₀bЛ)

2 шаг (q₀ c ® q₀ cЛ)

3 шаг (q₀ a ® q₁ aЛ)

4 шаг (q₁ d ® q₂ cП)

5 шаг (q₂ a ® q₅ dП)

Программа рассмотренной машины Тьюринга может быть представлена в виде таблицы соответствия:

А   Q	s0	a	b	c	d
q0		q1 aЛ	q0bЛ	q0 cЛ	-
q1		-	-	-	q2 cЛ
q2		q5 dП	-	-	-
q3		q4 dП	-	-	q2 bП
q4		-	-	-	-
q5	Останов

Запись алгоритма, реализуемого машиной Тьюринга, производится с помощью работы этой машины, представляющей собой совокупность команд. В рассматриваемом примере алгоритм переработки входного слова bcadc в слово bcdcc представляется командами:

(q₀ b ® q₀bЛ), (q₀ c ® q₀ cЛ), (q₀ a ® q₁ aЛ), (q₁ d ® q₂ cП), (q₂ a ® q₅ dП).

Алгоритмы пишутся столбцами. Для контроля против некоторых команд указывается слово, в которое переходит первоначально заданное слово после выполнения всех предыдущих команд, включая и стоящую слева команду.

Рассмотрим в качестве примера алгоритм переноса нуля для машины Тьюринга, программа которой задана следующей таблицей соответствия:

А   Q
q0	q0 0C	q0 1C
q1	q2 Л	-
q2	q3 1С	-
q3	q4 П	q3 Л
q4	-	q5 0C
q5	q6 П	-
q6	q0 0C	q6 П

Команды Конфигурация

q1 0 q2 Л	0 q2 010
q2 0 q3 1С	0 q3 110
q3 1 q3 Л	01 q3 10 ® 011 q3 0
q3 0 q4 П	01 q4 10
q4 1 q5 0С	01 q5 00
q5 0 q6 П	0 q6 100
q6 1 q6 П	q6 0100
q6 0 q0 0С	q0 0100

Как было показано, на машинах Тьюринга оказалось возможным осуществить или имитировать все алгоритмические процессы, которые когда-либо описывались математиками. Было доказано, что класс функций, вычислимый на этих машинах, точно совпадает с классом всех частично рекурсивных функций.

Вопрос о возможности или невозможности разрешающего алгоритма для задачи того или иного типа следует понимать как вопрос о существовании или несуществовании машины Тьюринга, обладающей нужным свойством.

Рассмотрим еще пример (здесь "П" и "Л" означают перемещение головки, а не ленты).

Как видно из таблицы, управляющее устройство может находиться в трех различных состояниях. Состояние q₀ особое. Оно соответствует выключенной машине.

	q0	q1	q2
	q0 0 С	q1 П	q0 1 С
	q2 1 С	q2 П	q2 1 П
+	q0 + С		q0 1 С

Как видно из первого столбца таблицы, в состоянии q₀ символы на ленте сохраняются неизменными, само состояние не меняется, и движения нет (С - стоп). Два других состояния - рабочие. Работа машины начинается с того, что управляющее устройство переводится в состояние q₁. При этом слово на ленте справа от местоположения "глаза" управляющего устройства. Пусть, например, имеется исходная ситуация:

00111+1100

q₁ q₁ 0 ® q₁ 0П

Местоположение управляющего устройства отмечено символом состояния q₁. Обратимся к таблице. В состоянии, считав символ 0, машина должна сохранить свое состояние и сдвинуться вправо на одну клетку ленты (П). После этого возникнет ситуация:

00111+1100

q₁ q₁ 0 ® q₁ 0П

Она аналогична предыдущей, и машина Тьюринга на этом такте выполнит сдвиг вправо на одну клетку, сохранив состояние q₁. В результате возникнет другая ситуация. Считав символ 1 в состоянии q₁, машина стирает его, заменяет на 0, меняет состояние на q₂ и сдвигается вправо на одну клетку ленты. Новая ситуация имеет вид:

00011+1100

q₂ q₁ 1 ® q₂ 0П

В состоянии q₂, как следует из таблицы управления, все символы 1 на ленте сохраняются, состояние q₂ тоже сохраняется, а управляющее устройство сдвигается вправо. Так будет происходить до тех пор, пока не возникнет ситуация:

q₂ 1 ® q₂ 1П

00011+1100

q₂ q₂ + ® q₀ 1С

Таблица управления в этой ситуации предписывает заменить + на единицу и прекратить работу.

Окончательная ситуация на ленте:

0001111100. Результат

Какую же работу выполнила машина? Если договориться интерпретировать слова ее входного языка как записи натуральных чисел, а + - как сложение, то машина, заданная таблицей управления, будет осуществлять операцию сложения натуральных чисел.

В примере - 3+2=5.

12. Елементи теорії нечітких множин. (2 год.)

Дата добавления: 2014-01-07