В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 5
Текст из файла (страница 5)
Строим множество N0 = {N |N → e}.Ш а г 2 . Строим множество Ni = Ni−1 ∪ {N |N → α, α ∈ {Ni−1 }∗ }.Ш а г 3 . Если Ni = Ni−1 , то перейти к шагу 4, иначе к шагу 2.Ш а г 4 . Если S ∈ Ni , то S → ∗ e.Легко видеть, что G′ — неукорачивающая грамматика. Можно показатьпо индукции, что L(G′ ) = L(G).Пусть Ki — класс всех языков типа i. Доказано, что справедливо следующее (строгое) включение: K3 ⊂ K2 ⊂ K1 ⊂ K0 .Заметим, что если язык порождается некоторой грамматикой, то это неозначает, что он не может быть порожден грамматикой с более сильнымиограничениями на правила. Приводимый ниже пример иллюстрирует этотфакт.Пример 2.8. Рассмотрим грамматику G = ({S , A, B}, {0, 1}, {S → AB , A → 0A,A → 0, B → 1B , B → 1}, S).
Эта грамматика является контекстно-свободной. Легкопоказать, что L(G) = {0n 1m |n, m > 0}. Однако в примере 2.7 приведена праволинейная грамматика, порождающая тот же язык.2.4. Машины ТьюрингаФормально машина Тьюринга — это совокупность M = (Q, Γ, Σ, D, q0 , F ),где:Q — конечное множество состояний;F ⊆ Q — множество заключительных состояний;Γ — множество допустимых ленточных символов; один из них, обычнообозначаемый B , — пустой символ;Σ — множество входных символов: подмножество Γ, не включающее B ;D — функция переходов, отображение из (Q − F )× Γ → Q × Γ × {L, R};для некоторых аргументов функция D может быть не определена.q0 — начальное состояние.Схематически машина Тьюринга изображена на рис.
2.1.Рис. 2.1 Машина ТьюрингаОпределенная таким образом машина Тьюринга называется детерминированной. Недетерминированная машина Тьюринга для каждой пары(Q − F ) × Γ может иметь несколько возможных переходов. В начале n ячеекленты содержат вход w ∈ (Γ − {B})∗ , остальная часть ленты содержит пустые символы. Обозначим конфигурацию машины Тьюринга как (q , w, i), где2.4. Машины Тьюринга21q ∈ Q — текущее состояние, i — выделенный элемент строки, «положениеголовки», w — текущее содержимое занятого участка ленты. Если головкасдвигается с ячейки, то машина должна записать в нее символ, так что лентавсегда состоит из участка, состоящего из конечного числа непустых символови бесконечного количества пустых символов.Определим на конфигурациях отношение ⊢ (шаг) следующим образом.Пусть (q , A1 , A2 , .
. . An , i) – конфигурация M , где 1 6 i 6 n + 1.Если 1 6 i 6 n и D(q , Ai ) = (p, A, R) (R от англ. right — правый),то A 6= B и (q , A1 A2 . . . An , i)|− M (p, A1 A2 . . . Ai−1 AAi+1 . . . An , i + 1), т. е. Mпечатает символ A и передвигается вправо.Если 2 6 i 6 n и D(q , Ai ) = (p, A, L) (L от англ. left — левый), то при i = nдопустимо A = B и (q , A1 A2 .
. . An , i)|− M (p, A1 A2 . . . Ai−1 AAi+1 . . . An , i − 1),M печатает A и передвигается влево, но не за конец ленты.Если i = n + 1, головка просматривает пустой символ B .Если D(q , B) = (p, A, R), то A 6= B и (q , A1 A2 . . . An , n + 1)|− M (p, A1 A2 . . .. . . An A, n + 2).Если D(q , B) = (p, A, L), то допустимо A = B и (q , A1 A2 . . . An , n + 1)|−− M (p, A1 A2 . . . An A, n).Если две конфигурации связаны отношением |− M , то мы говорим, чтовторая получается из первой за один шаг.
Если вторая получается из первойза конечное, включая 0, число шагов, то такое отношение будем обозначать|− ∗M .Язык, допускаемый M , — это множество таких слов из T ∗ , которые,будучи расположены в левом конце ленты, переводят M из начального состояния q0 с начальным положением головки в самом левом конце лентыв конечное состояние. Формально, язык, допускаемый M , это L = {w | w ∈ Σ∗и (q0 , w, 1)|− ∗M (q , u, i) для некоторых q ∈ F , u ∈ Γ∗ и целого i}.Если M распознаёт L, то M останавливается, т.
е. не имеет переходов после того, как слово допущено. Однако если слово не допущено, то возможно,что M не останавливается.Язык, допускаемый некоторой M , называется рекурсивно перечислимым.Если M останавливается на всех входах, то говорят, что M задает алгоритм,а язык называется рекурсивным.Существует машина Тьюринга, которая по некоторому описанию произвольной M и кодированию слова x моделирует поведение M со входом x.Такая машина Тьюринга называется универсальной машиной Тьюринга.2.4.1.
Неразрешимость проблемы останова. Проблема останова длямашины Тьюринга формулируется следующим образом: можно ли по данноймашине Тьюринга в произвольной конфигурации со строкой конечной длинынепустых символов на ленте определить, остановится ли она? Говорят, что22Глава 2. Языки и их представлениеэта проблема рекурсивно неразрешима: это означает, что не существуеталгоритма, который для любой M в произвольной конфигурации определялбы, остановится ли в конце концов M .Перенумеруем все машины Тьюринга и все возможные входы над алфавитом Σ. Рассмотрим языкL1 = {xi | xi не допускается Ti }.Ясно, что L1 не допускается никакой M .
Допустим, что это не так. ПустьL1 допускается Tj . Следовательно xj ∈ L1 тогда и только тогда, когда xjне допускается Tj . Но поскольку Tj допускает L1 , xj ∈ L1 тогда и толькотогда, когда допускается Tj , — противоречие. Поэтому L1 не является рекурсивно перечислимым множеством.Предположим, что мы имеем алгоритм (т. е. машину Тьюринга, котораявсегда останавливается), позволяющий определить, остановится ли машинаТьюринга в данной конфигурации.
Тогда машину Тьюринга T , допускающуюL1 , можно построить следующим образом.1. Если дано слово x, то T перечисляет слова x1 , x2 , . . ., пока не будетxi = x.2. T генерирует кодировку машины Тьюринга Ti .3. Управление передается гипотетической машине, которая определяет,останавливается ли Ti на входе xi .4. Если выясняется, что Ti не останавливается на входе xi , то T останавливается и допускает xi .5. Если выясняется, что Ti останавливается на входе xi , то управлениепередается универсальной машине Тьюринга, которая моделирует Ti на входеxi .
Поскольку Ti останавливается, универсальная машина Тьюринга тожеостанавливается и определяет, допускает ли Ti слово xi .В любом случае T останавливается, допуская xi в том случае, когда Tiотвергает xi , и отвергая xi , когда Ti допускает xi .Таким образом, из нашего предположения, что существует машина Тьюринга, которая определяет, останавливается ли произвольная машина Тьюринга, следует, что L1 допускается некоторой машиной Тьюринга, а это противоречит доказанному выше. Это, в свою очередь, дает следующую теорему.Теорема 2.2. Не существует алгоритма для определения того, остановится ли произвольная машина Тьюринга в произвольной конфигурации.2.4.2. Класс рекурсивных множеств. Теперь можно показать, чтокласс рекурсивных множеств является собственным подклассом класса рекурсивно перечислимых множеств.
Это значит, что существует множество,слова которого могут быть распознаны машиной Тьюринга, которая не останавливается на некоторых словах, не принадлежащих множеству, но оно2.4. Машины Тьюринга23не может быть распознано никакой машиной Тьюринга, которая останавливается на всех словах.
Примером такого множества является дополнение к L1 .Лемма 2.1. Если множество рекурсивно, то и его дополнение рекурсивно.Д о к а з а т е л ь с т в о . Если L — рекурсивное множество, L ⊆ T ∗ , тосуществует M , допускающая L и гарантированно останавливающаяся. Можно считать, что после допуска M больше не делает шагов. Построим M1по M , добавив новое состояние q как единственное допускающее состояниеM1 . Правила M1 включают все правила M , так что M1 симулирует M .Кроме того, для каждой пары, составленной из недопускающего состояния иленточного символа M , для которых у M переход не определен, M1 переходитв состояние q и затем останавливается.Таким образом M1 симулирует M вплоть до остановки.
Если M останавливается в одном из допускающих состояний, то M1 останавливается бездопуска. Если M останавливается в одном из недопускающих состояний, то,значит, M1 не допускает входное слово. Тогда M1 делает еще один переходв состояние q и допускает. Ясно, что M1 допускает T ∗ \ L.Лемма 2.2. Пусть x1 , x2 , . . . — нумерация всех слов некоторого конечного алфавита Σ и T1 , T2 , . . . — нумерация всех машин Тьюрингас ленточными символами, выбранными из некоторого конечного алфавита, включающего Σ. Пусть L2 = {xi | xi допускается Ti }. Тогда L2 —рекурсивно перечислимое множество, дополнение которого не рекурсивноперечислимо.Д о к а з а т е л ь с т в о . Слова L2 допускаются некоторой M , работающей следующим образом (отметим, что M не обязательно останавливаетсяна словах не из L2 ).1.
Если дано x, то M перечисляет предложения x1 , x2 , . . . пока не найдетxi = x, определяя тем самым, что x — это i-е слово в перечислении.2. M генерирует Mi и передает управление универсальной машине Тьюринга, которая симулирует Mi со входом x.3. Если Mi останавливается со входом xi и допускает, то M останавливается и допускает; если Mi останавливается и отвергает xi , то Mостанавливается и отвергает xi . Наконец, если Mi не останавливается,то M не останавливается.4. Таким образом, L2 рекурсивно перечислимо, поскольку L2 — это множество, допускаемое M . Но дополнение ∼L2 к L2 не может быть рекурсивно перечислимо, поскольку если Tj — машина Тьюринга, допускающая∼L2 , то xj ∈ ∼L2 тогда и только тогда, когда xj не допускается Mj .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
