Языки и их представление

2. Лекция: Языки и их представление
В данной лекции рассматривается понятие языков и их представление. Приведены такие определения, как алфавит, цепочка, грамматика, машина Тьюринга. Также приведены примеры практической реализации основных понятий в теории программирования.

Алфавиты, цепочки и языки

Алфавит, или словарь - это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквами и специальными литерами типа

Пусть V - алфавит. Цепочка в алфавите V - это любая строка конечной длины, составленная из символов алфавита V . Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) - это цепочка, в которую не входит ни один символ.

Конкатенацией цепочек x и y называется цепочка xy. Заметим, что xe = ex = x для любой цепочки x.

Пусть x, y, z - произвольные цепочки в некотором алфавите. Цепочка y называется подцепочкой цепочки xyz. Цепочки x и y называются, соответственно, префиксом и суффиксом цепочки xy. Заметим, что любой префикс или суффикс цепочки является подцепочкой этой цепочки. Кроме того, пустая цепочка является префиксом, суффиксом и подцепочкой для любой цепочки.

Пример 2.1. Для цепочки abbba префиксом является любая цепочка из множества суффиксом является любая цепочка из множества подцепочкой является любая цепочка из множества

Длиной цепочки w (обозначается |w|) называется число символов в ней. Например, |abababa| = 7, а |e| = 0. Язык в алфавите V - это некоторое множество цепочек в алфавите V.

Пример 2.2. Пусть дан алфавит V = {a, b}. Вот некоторые языки в алфавите V:

1. — пустой язык;
2. - язык, содержащий только пустую цепочку (заметим, что и - различные языки)
3. - язык, содержащий цепочки из a и b, длина которых не превосходит 2
4. - язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b
5. - язык цепочек из a, длины которых представляют собой квадраты натуральных чисел.

Рекомендуемые материалы

Два последних языка содержат бесконечное число цепочек.

Введем обозначение для множества всех цепочек в алфавите , включая пустую цепочку. Каждый язык в алфавите V является подмножеством . Для обозначения множества всех цепочек в алфавите V , кроме пустой цепочки, будем использовать .

Пример 2.3. Пусть . Тогда

Введем некоторые операции над языками.

Пусть и - языки в алфавите V . Конкатенацией языков и называется язык .

Пусть L - язык в алфавите V . Итерацией языка L называется язык , определяемый следующим образом:

Пример 2.4. Пусть и . Тогда

, и

Большинство языков, представляющих интерес, содержат бесконечное число цепочек. При этом возникают три важных вопроса.

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

Во-вторых, для любого ли языка существует конечное представление? Можно предположить, что ответ отрицателен. Мы увидим, что множество всех цепочек над алфавитом счетно. Язык - это любое подмножество цепочек. Из теории множеств известно, что множество всех подмножеств счетного множества несчетно. Хотя мы и не дали строгого определения того, что является конечным представлением, интуитивно ясно, что любое разумное определение конечного представления ведет только к счетному множеству конечных представлений, поскольку нужно иметь возможность записать такое конечное представление в виде строки символов конечной длины. Поэтому языков значительно больше, чем конечных представлений.

В-третьих, можно спросить, какова структура тех классов языков, для которых существует конечное представление?

Представление языков

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

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

Такой метод представляет язык с точки зрения распознавания. Язык можно также представить методом порождения. А именно, можно дать процедуру, которая систематически порождает в определенном порядке цепочки языка.

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

Предположим, что V имеет p символов. Мы можем рассматривать цепочки из как числа, представленные в базисе p, плюс пустая цепочка e. Можно занумеровать цепочки в порядке возрастания длины и в "числовом" порядке для цепочек одинаковой длины. Такая нумерация для цепочек языка приведена на рис. 2.1, а.

Пусть P - процедура для проверки принадлежности цепочки языку L. Предположим, что P может быть представлена дискретными шагами, так что имеет смысл говорить об i-ом шаге процедуры для любой данной цепочки. Прежде чем дать процедуру перечисления цепочек языка L, дадим процедуру нумерации пар положительных чисел.

Все упорядоченные пары положительных чисел (x, y) можно отобразить на множество положительных чисел следующей формулой:

z = (x + y - 1)(x + y - 2)/2 + y

Пары целых положительных чисел можно упорядочить в соответствии со значением z (рис. 2.1, б).

Рис. 2.1.

Теперь можно дать процедуру перечисления цепочек L. Нумеруем упорядоченные пары целых положительных чисел - (1,1), (2,1), (1,2), (3,1), (2,2), ... . При нумерации пары (i, j) генерируем i-ю цепочку из V* и применяем к цепочке первые j шагов процедуры P. Как только мы определили, что сгенерированная цепочка принадлежит L, добавляем цепочку к списку элементов L. Если цепочка i принадлежит L, это будет определено P за j шагов для некоторого конечного j. При перечислении (i; j) будет сгенерирована цепочка с номером i. Легко видеть, что эта процедура перечисляет все цепочки L.

Если мы имеем процедуру генерации цепочек языка, то мы всегда можем построить процедуру распознавания предложений языка, но не всегда алгоритм. Для определения того, принадлежит ли x языку L, просто нумеруем предложения L и сравниваем x с каждым предложением. Если сгенерировано x, процедура останавливается, распознав, что x принадлежит L. Конечно, если x не принадлежит L, процедура никогда не закончится.

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

Грамматики

Формальное определение грамматики

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

Определение. Грамматика - это четверка G = (N,T,P,S), где

(1) N - алфавит нетерминальных символов;

(2) T - алфавит терминальных символов,

(3) P - конечное множество правил вида , где

(4) - начальный знак (или аксиома) грамматики.

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

Будем использовать также сокращенную запись для обозначения группы правил

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

Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения , а также его степень (обозначаемые соответственно , и ). Если , то говорят, что цепочка выводима (нетривиально выводима, выводима за k шагов) из .

Если , то существует последовательность шагов

где и . Последовательность цепочек в этом случае называют выводом из

Сентенциальной формой грамматики G называется цепочка, выводимая из ее начального символа.

Языком, порождаемым грамматикой G (обозначается L(G)), называется множество всех ее терминальных сентенциальных форм, то есть

Грамматики G1 и G2 называются эквивалентными, если они порождают один и тот же язык, то есть

Пример 2.5. Грамматика G = ({S, B, C}, {a, b, c}, P, S), где , порождает язык

Действительно, применяем n - 1 раз правило 1 и получаем , затем один раз правило 2 и получаем , затем n(n - 1)/2 раз правило 3 и получаем .

Затем используем правило 4 и получаем aⁿbB^n-1Cⁿ . Затем применяем n - 1 раз правило 5 и получаем aⁿbⁿCⁿ. Затем применяем правило 6 и n - 1 раз правило 7 и получаем aⁿbⁿcⁿ . Можно показать, что язык L(G) состоит из цепочек только такого вида.

Пример 2.6. Рассмотрим грамматику . Легко видеть, что цепочка , так как существует вывод

Нетрудно показать, что грамматика порождает язык .

Пример 2.7. Рассмотрим грамматику . Нетрудно показать, что грамматика порождает язык

Типы грамматик и их свойства

Рассмотрим классификацию грамматик (предложенную Н.Хомским), основанную на виде их правил.

Определение. Пусть дана грамматика G = (N, T, P, S). Тогда

(1) если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений.

(2) если

1. каждое правило грамматики, кроме , имеет вид , где , и
2. в том случае, когда , символ S не встречается в правых частях правил, то грамматику называют грамматикой типа 1, или неукорачивающей или контекстно-зависимой (КЗ- грамматикой) или контекстно - чувствительной (КЧ- грамматикой).

(3) если каждое правило грамматики имеет вид , где , то ее называют грамматикой типа 2, или контекстно-свободной (КС-грамматикой).

(4) если каждое правило грамматики имеет вид либо , либо , где то ее называют грамматикой типа 3, или праволинейной.

Легко видеть, что грамматика в примере 2.5 - неукорачивающая, в примере 2.6 - контекстно-свободная, в примере 2.7 - праволинейная.

Язык, порождаемый грамматикой типа i, называют языком типа i. Язык типа 0 называют также языком без ограничений, язык типа 1 - контекстно-зависимым (КЗ), язык типа 2 - контекстно-свободным (КС), язык типа 3 - праволинейным.

Теорема 2.1. Каждый контекстно-свободный язык может быть порожден неукорачивающей контекстно- свободной грамматикой.

Доказательство. Пусть L - контекстно-свободный язык. Тогда существует контекстно-свободная грамматика G = (N, T, P, S), порождающая L.

Построим новую грамматику G' = (N',T,P',S') следующим образом:

1. Если в P есть правило вида , где для и ни из одной цепочки не выводится e, то включить в P' все правила (кроме ) вида

где это либо , либо e.

1. Если , то включить в P' правила и положить . В противном случае положить и . Порождает ли грамматика пустую цепочку можно установить следующим простым алгоритмом:

Шаг 1. Строим множество

Шаг 2. Строим множество

Шаг 3. Если , перейти к шагу 4, иначе шаг 2.

Шаг 4. Если , значит .

Легко видеть, что - неукорачивающая грамматика. Можно показать по индукции, что .

Пусть K_i - класс всех языков типа i. Доказано, что справедливо следующее (строгое) включение: .

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

Пример 2.8. Рассмотрим грамматику . Эта грамматика является контекстно-свободной. Легко показать, что . Однако, в примере 2.7 приведена праволинейная грамматика, порождающая тот же язык.

Ниже приводятся подробные примеры решения двух практически интересных более сложных задач на построение КС- и НС-грамматик.

Пример 2.9. Данный пример относится к несколько парадоксальной для грамматик постановке: построить КС- грамматику, порождающую язык:

т.е. построить все цепочки кроме указанных (обычно-то говорят о том, что надо построить). Но, может быть, в такой постановке заложена и подсказка к решению? Известно, что иные задачи с подобными требованиями так и решаются: нужно сделать все, "что не надо", а потом отклониться от этого "не надо" всеми возможными способами.

Однако воодушевл_нных построением в рамках КС- грамматики цепочек вида (здесь и далее в этом примере ждет некоторое разочарование. Действительно, в отличие от таких случаев, как , , и т.п., обе зависимости (по n и по m) придется отслеживать одновременно и из двух разных центров порождения, к чему КС-грамматики по своей природе (виду своих правил) оказываются не предназначены.

Попробуем тогда пересказать условие задачи в конструктивном (созидательном) плане, т.е. обозначая лишь то, что нам нужно построить, а не наоборот. Поначалу такое множество цепочек кажется необозримым. Но попробуем, "Дорогу осилит идущий"! Начнем с очевидных случаев:

Однако бесконечно продолжать в духе уже как- то скучно. Замечаем, что вполне конечным образом определяет половину из упомянутых бесчисленных описаний, а в следующий момент симметрия нам подсказывает и язык .

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

Далее рассмотрим случай . Но что такое, к примеру, ? То же самое, что объединение условий ! И здесь перешли к конструктиву, который несложно строится в рамках КС-грамматики.

Остается единственный неупомянутый случай:

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

Так, если язык может быть порожден грамматикой

а язык - грамматикой

то для объединения этих языков (в общем случае использующих каждый свой уникальный набор вспомогательных знаков) достаточно добавить правило старта из новой общей аксиомы:

Пример 2.10. Построение НС-грамматики.

Грамматики непосредственных составляющих (или, кратко, НС-грамматики) есть вид представления контекстно-зависи- мых грамматик, т.е. они обладают теми же выразительными возможностями, что и КЗ-грамматики в целом. Каждое правило НС-грамматики должно соответствовать виду:

то есть левое и правое окружение (контекст) заменяемого знака A должны сохраниться и вокруг непустой заменяющей цепочки (греческая буква "эта".

Такое дополнительное ограничение позволяет удобнее переходить от КЗ-грамматики к соответствующему линейно- ограниченному автомату

Рассмотрим построение НС-грамматики для языка

, порождающего слова вида

Для большей ясности сперва построим для этого языка грамматику общего вида, а потом перестроим ее в соответствии с НС-ограничениями.

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

Итак, порождаем две группы по n элементов

Получили , но что делать с C и D? Сделав свое дело, они стали лишними.

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

Поэтому в обоих случаях не обойтись без дальнейшего уточнения предназначения (миссий) и состава "действующих лиц". Отметим для этого самый первый из команды знаков C (назовем его B) и самый последний из D (обозначим его E). Когда B и E встретятся, это и будет признаком полного завершения процесса порождения знаков a.

Начнем вывод с начала:

Результат получили, но какой ценой (для B, C, D и E)? Прямо-таки сталинские методы. Точнее скажем, в военных или иных чрезвычайных условиях иначе, порой, и нет возможности поступить. А в более мирное время? Попробуем "соблюдать КЗОТ" и обойтись без сокращений.

Снова:

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

Мы получили несокращающую грамматику. Но широко используемые при ее построении правила вида ( и т.п.), очевидно, не подходят под определение НС-грамматики (убедитесь!). Такие "рокировки" , однако, легко раскрыть через цепочку правил вида

где и - нигде более в грамматике не используемые вспомогательные знаки. Отметим, что замену на промежуточные знаки и обратно на исходные нужно осуществлять в одном и том же порядке (слева-направо или, наоборот, только справа-налево), иначе в общем случае (когда назначение A и B в грамматике различно) возникают лишние цепочки.

Так, применение замены

(нарушен порядок замен) при наличии соответствующего прово- кационного окружения допускает подмену B на A:

Замена AB на BA в рамках НС-грамматики коротко обозначается, как и обычный вывод: .

Таким образом, один из возможных наборов правил искомой НС-грамматики имеет следующий вид:

Машины Тьюринга

Формально машина Тьюринга (Tm) - это , где

Q - конечное множество состояний;

- множество заключительных состояний;

- множество допустимых ленточных символов; один из них, обычно обозначаемый B, - пустой символ

- множество входных символов, подмножество Gamma, не включающее B,

D функция переходов, отображение из для некоторых аргументов функция D может быть не определена.

- начальное состояние.

Рис. 2.2. Машина Тьюринга

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

Шаг Tm определим следующим образом.

Пусть (q, A₁, A₂, ... A_n, i) - конфигурация Tm,

где .

Если и D(q, A_i) = (p, A, R)

(R от англ. Right), то и)

То есть Tm печатает символ A и передвигается вправо.

Если и

(L от англ. Left), то если i = n, то допустимо A = B и

Tm печатает A и передвигается влево, но не за конец ленты.

Если i = n + 1, головка просматривает пустой символ B.

Если D(q, B) = (p, A, R), то и

Если D(q, B) = (p, A, L), то допустимо A=B и

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

Язык, допускаемый Tm, это множество таких слов из T^*, которые будучи расположены в левом конце ленты переводят Tm из начального состояния q₀ с начальным положением головки в самом левом конце ленты в конечное состояние. Формально, язык, допускаемй Tm, это

Если Tm распознает L, то Tm останавливается, то есть не имеет переходов после того, как слово допущено. Однако, если слово не допущено, возможно, что Tm не останавливается.

Язык, допускаемый некоторой Tm, называется рекурсивно перечислимым. Если Tm останавливается на всех входах, то говорят, что Tm задает алгоритм и язык называется рекурсивным.

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

Неразрешимость проблемы останова

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

Перенумеруем все машины Тьюринга и все возможные входы над алфавитом . Рассмотрим язык

L₁={x_i|x_i не допускается T_i}

Ясно, что не допускается никакой Tm. Допустим, что это не так. Пусть допускается Tj . Тогда тогда и только тогда, когда не допускается . Но поскольку допускает тогда и только тогда, когда допускается , - противоречие. Так что - не является рекурсивно перечислимым множеством.

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

1. Если дано слово x, T перечисляет слова x₁, x₂... пока не будет x_i = x.
2. T генерирует кодировку машины Тьюринга T_i.
3. Управление передается гипотетической машине, которая определяет останавливается ли T_i на входе x_i.
4. Если выясняется, что T_i не останавливается на входе x_i, то T останавливается и допускает x_i.
5. Если выясняется, что T_i останавливается на входе x_i, то управление передается универсальной машине Тьюринга, которая моделирует T_i на входе x_i. Поскольку T_i в конце концов останавливается, универсальная машина Тьюринга в конце концов останавливается и определяет допускает ли T_i слово x_i.

В любом случае T останавливается, допуская x_i в том случае, когда T_i отвергает x_i, и отвергая x_i, когда T_i допускает x_i.

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

Теорема 2.2. Не существует алгоритма для определения того, остановится ли произвольная машина Тьюринга в произвольной конфигурации.

Класс рекурсивных множеств

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

Лемма 2.1. Если множество рекурсивно, то и его дополнение рекурсивно.

Доказательство. Если L - рекурсивное множество, , то существует Tm допускающая L и гарантированно останавливающаяся. Можно считать, что после допуска Tm не делает больше шагов. Построим Tm₁ по Tm, добавив новое состояние q как единственное допускающее состояние Tm₁. Правила Tm₁ включают все правила Tm, так что Tm₁ симулирует Tm. Кроме того, для каждой пары, составленной из недопускающего состояния и ленточного символа Tm, для которых у Tm переход не определен, Tm₁ переходит в состояние q и затем останавливается.

Таким образом Tm₁ симулирует Tm вплоть до остановки. Если Tm останавливается в одном из допускающих состояний, Tm₁ останавливается без допуска. Если Tm останавливается в одном из недопускающих состояний, значит не допускает вход. Тогда Tm₁ делает еще один переход в состояние q и допускает. Ясно, что Tm₁ допускает T^*L.

Лемма 2.2. Пусть - нумерация всех слов некоторого конечного алфавита - и T₁, T₂, ... - нумерация всех машин Тьюринга с ленточными символами, выбранными из некоторого конечного алфавита, включающего -. Пусть допускается . L₂ - рекурсивно перечислимое множество, дополнение которого не рекурсивно перечислимо.

Доказательство. Слова L₂ допускаются некоторой Tm, работающей следующим образом. Отметим, что Tm не обязательно останавливается на словах не из L₂.

1. Если дано x,Tm перечисляет предложения x₁, x₂,... пока не найдет x_i = x, определяя тем самым, что x - это i-е слово в перечислении.
2. Tm генерирует Tm_i и передает управление универсальной машине Тьюринга, которая симулирует Tm_i со входом x.
3. Если Tm_i останавливается со входом x_i и допускает, Tm останавливается и допускает; если Tm_i останавливается и отвергает x_i, то Tm останавливается и отвергает x_i. Наконец, если Tm_i не останавливается, то Tm не останавливается.
4. Таким образом L₂ рекурсивно перечислимо, поскольку L₂ - это множество допускаемое Tm. Но дополнение к не может быть рекурсивно перечислимо, поскольку если T_j - машина Тьюринга, допускающая тогда и только тогда, когда x_j не допускается Tm_j . Это противоречит утверждению, что - это язык, допускаемый T_j .

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

Доказательство. Доказательство. По лемме 2.2 L₂ - рекурсивно перечислимое множество, дополнение которого не рекурсивно перечислимо. Если бы L₂ было рекурсивно, по лемме было бы рекурсивно, и следовательно рекурсивно перечислимо, что противоречит второй половине леммы 2.2.

Связь машин Тьюринга и грамматик типа 0

Докажем, что язык распознается машиной Тьюринга тогда и только тогда, когда он генерируется грамматикой типа 0. Для доказательства части "если" мы построим недетерминированную машину Тьюринга, которая будет Связь машин Тьюринга и грамматик типа 0 35 недетерминированно выбирать выводы в грамматике и смотреть, является ли вывод входом. Если да, машина допускает вход.

Для доказательства части "только если" мы построим грамматику, которая недетерминированно генерирует представления терминальной строки и затем симулирует машину Тьюринга на этой строке. Если строка допускается некоторой Tm, строка конвертируется в терминальные символы, которые она представляет.

Теорема 2.4. Если L генерируется грамматикой типа 0, то L распознается машиной Тьюринга.

Доказательство. Пусть - грамматика типа 0 и L = L(G). Опишем неформально недетерминированную машину Тьюринга Tm, допускающую L.

где

Предполагается, что последние три символа не входят в .

Вначале Tm содержит на входной ленте . Tm вставляет # перед w, сдвигая все символы w на одну ячейку вправо, и #S# после w, так что содержимым ленты становится #w#S#.

Теперь Tm недетерминированно симулирует вывод в G, начиная с S. Каждая сентенциальная форма вывода появляется по порядку между последними двумя #. Если некоторый выбор переходов ведет к терминальной строке, она сравнивается с w. Если они совпадают, Tm допускает.

Формально, пусть Tm имеет на ленте #w#A₁A₂...A_k#. Tm передвигает недетерминированно головку по A₁A₂...A_k, выбирая позицию i и константу r между 1 и максимальной длиной левой части любого правила вывода в P. Затем Tm проверяет подстроки A_iA_i+1...A_i+r-1. Если A_iA_i+1...A_i+r-1 - левая часть некоторого правила вывода из P, она может быть заменена на правую часть. Tm может сдвинуть A_i+rA_i+r+1...A_k# либо влево, либо вправо, освобождая или заполняя место, если правая часть имеет длину, отличную от r.

Из этой простой симуляции выводов в G видно, что Tm печатает на ленте строку вида в точности, если . Если y = w, Tm допускает L.

Теорема 2.5. Если L распознается некоторой машиной Тьюринга,то L генерируется грамматикой типа 0.

Доказательство. Пусть допускает L. Построим грамматику G, которая недерминированно генерирует две копии представления некоторого слова из и затем симулирует поведение Tm на одной из копий. Если Tm допускает слово, то G трансформирует вторую копию в терминальную строку. Если Tm не допускает L, то вывод никогда не приводит к терминальной строке.

Формально, пусть

, где

Продукции таковы:

2. для каждого
6. для каждого и каждого и такого, что
7. для каждого C, J, I из , a и b
8. для каждого

Используя правила 1 и 2

где для некоторого

Предположим, что Tm допускает строку a₁a₂ ... a_n. Тогда для некоторого m Tm использует не более, чем m ячеек справа от входа. Используя правило 3, затем правило 4 m раз, и наконец, правило 5, имеем

Начиная с этого момента могут быть использованы только правила 6 и 7, пока не сгенерируется допускающее состояние. Отметим, что первые компоненты ленточных символов в никогда не меняются. Индукцией по числу шагов Tm можно показать, что если

, то

где a₁, a₂, ... a_n принадлежат , a_n+1 = a_n+2 = ... a_n+m = e,

X₁ X₂, ...X_n+m принадлежат и X_S+1=X_S+2=...X_n+m=B

Предположение индукции тривиально для нуля шагов. Предположим, что оно справедливо для k - 1 шагов. Пусть

за k шагов. По предположению индукции

Пусть E = L, если j₂ = j₁ - 1 и E = R, если j₂ = j₁ + 1. В этом случае D(q₁, X_j1 ) = (q₂, Y_j1, E).

По правилам 6 или 7

в зависимости от того, равно ли E значению R или L.

Теперь X_i = Y_i для всех .

Таким образом,

что доказывает предположение индукции.

По правилу 8, если , легко показать, что

Таким образом, G может генерировать a₁a₂ ... a_n, если a₁a₂ ... a_n допускается Tm. Таким образом, L(G) включает все слова, допускаемые Tm. Для завершения доказательства необходимо показать, что все слова из L(G) допускаются Tm. Индукцией доказывается, что только если w допускается Tm.

Линейно-ограниченные автоматы и их связь с контекстно-зависимыми грамматиками

Каждый КЗ-язык является рекурсивным, но обратное не верно. Покажем что существует алгоритм, позволяющий для произвольного КЗ-языка L в алфавите T, и произвольной цепочки определить, принадлежит ли w языку L.

Теорема 2.6. Каждый контекстно-зависимый язык является рекурсивным языком.

Доказательство. Пусть L - контекстно-зависимый язык. Тогда существует некоторая неукорачивающая грамматика G = (N, T, P, S), порождающая L.

Пусть . Если n = 0, то есть w = e, то принадлежность проверяется тривиальным образом. Так что будем предполагать, что n > 0.

Определим множество Tm как множество строк длины не более n таких, что вывод имеет не более m шагов. Ясно, что T₀ = {S}.

Легко показать, что T_m можно получить из T_m-1 просматривая, какие строки с длиной, меньшей или равной n можно вывести из строк из T_m-1 применением одного правила, то есть

Если и для некоторого m. Если из S не выводится u или |u| > n, то u не принадлежит T_m ни для какого m.

Очевидно, что для всех m > 1. Поскольку T_m зависит только от T_m-1, если Tm = T_m-1, то T_m = T_m+1 = T_m+2 = ... . Процедура будет вычислять T₁, T₂, T₃, . . . пока для некоторого m не окажется T_m = T_m-1. Если w не принадлежит T_m, то не принадлежит и L(G), поскольку для j > m выполнено T_j = T_m. Если то .

Покажем, что существует такое m, что T_m = Tm-1. Поскольку для каждого i > 1 справедливо , то если , то число элементов в T_i по крайней мере на 1 больше, чем в T_i-1. Пусть . Тогда число строк в длины меньшей или равной n равно . Только эти строки могут быть в любом T_i. Значит, T_m = T_m-1 для некоторого . Таким образом, процедура, вычисляющая T_i для всех до тех пор, пока не будут найдены два равных множества, гарантированно заканчивается, значит, это алгоритм.

Линейно-ограниченный автомат (ЛОА) - это недетерминированная машина Тьюринга с одной лентой, которая никогда не выходит за пределы |w| ячеек, где w - вход. Формально, линейно-ограниченный автомат обозначается как . Обозначения имеют тот же смысл, что и для машин Тьюринга. Q - это множество состояний, - множество заключительных состояний, - множество ленточных символов, - множество входных символов, - начальное состояние, D- отображение из Q x Γ в подмножество Q x Γ x {L, R}.

Σ содержит два специальных символа, обычно обозначаемых © и $, - левый и правый концевые маркеры, соответственно. Эти символы располагаются сначала по концам входа и их функция - предотвратить переход головки за пределы области, в которой расположен вход.

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

(q,A₁A₂,...,A_n,i) где -целое от 1 до n. Предположим, что и i > 1

Будем говорить, что

и i < n, будем говорить, что

То есть M печатает A поверх A_i, меняет состояние на p и передвигает головку влево или вправо, но не за пределы области, в которой символы располагались исходно. Как обычно, определим отношение как

и

Если и ,

то

Язык, допускаемый M - это и для некоторого и целого i}.

Будем называть M детерминированным, если D(q, A) содержит не более одного элемента для любых . Не известно, совпадает ли класс множеств, допускаемых детерминированными и недетеминированными ЛОА. Ясно, что любое множество, допускаемое недетерминированным ЛОА, допускается некоторой детерминированной МТ. Однако, число ячеек ленты, требуемой этой МТ, может экспоненциально зависеть от длины входа.

Класс множеств, допускаемых ЛОА, в точности совпадает с классом контекстно - зависимых языков.

Теорема 2.7. Если L - контекстно-зависимый язык, то L допускается ЛОА.

Доказательство. Пусть G = (V_N, V_T, P, S) - контекстно- зависимая грамматика. Построим ЛОА M такой, что он допускает язык L(G). Не вдаваясь в детали построения M, поскольку он довольно сложен, рассмотрим схему его работы. В качестве ленточных символов будем рассматривать пары В начальной конфигурации лента содержит (@, B), (a₁, B), ... (a_n, B), ($, B), где a¹ ... a_n = w - входная цепочка, n=|w|. Цепочку символов n будем называть " первым треком ", n - " вторым треком ". Первый трек будет содержать входную строку x с концевыми маркерами. Второй трек будет использоваться для вычислений. На первом шаге M помещает символ S в самой левой ячейке второго трека. Затем M выполняет процедуру генерации в соответствии со следующими шагами:

1. Процедура выбирает подстроку символов из второго трека такую, что .
2. Подстрока заменяется на β, перемещая, если необходимо, вправо символы справа от . Если эта операция могла бы привести к перемещению символа за правый концевой маркер, ЛОА останавливается.
3. Процедура недетерминированно выбирает перейти на шаг 1 или завершиться.

На выходе из процедуры первый трек все еще содержит строку x, а второй трек содержит строку γ такую, что ЛОА сравнивает символы первого трека с соответствующими символами второго трека. Если сравнение неуспешно, строки символов первого и второго треков не одинаковы и ЛОА останавливается без допуска. Если строки одинаковы, ЛОА останавливается и допускает.

Если , то существует некоторая последовательность шагов, на которой ЛОА строит x на втором треке и допускает вход. Аналогично, для того, чтобы ЛОА допустил x, должна существовать последовательность шагов такая, что x может быть построен на втором треке. Таким образом, должен быть вывод x из S в G.

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

Теорема 2.8. Если L допускается ЛОА, то L - контекстно - зависимый язык.

Доказательство. Конструкция КЗГ по ЛОА аналогична конструкции грамматики типа 0, моделирующей машину Тьюринга. Различие заключатся в том, что нетерминалы КЗГ должны указывать не только текущее и исходное содержимое ячеек ленты ЛОА, но и то, является ли ячейка соседней справа или слева с концевым маркером. Кроме того, состояние ЛОА должно комбинироваться с символом под головкой, поскольку КЗГ не может иметь раздельные символы для концевых маркеров и состояния ЛОА, так как эти символы должны были бы быть заменены на e, когда строка превращается в терминальную.

Ещё посмотрите лекцию "17 - Физиология компонентов крови" по этой теме.

Теорема 2.9. Существуют рекурсивные множества, не являющиеся контекстно - зависимыми.

Доказательство. Все строки в {0,1}^* можно занумеровать. Пусть x_i - i-ое слово. Мы можем занумеровать все грамматики типа 0, терминальными символами которых являются 0 и 1. Поскольку имена переменных не важны и каждая грамматика имеет конечное их число, можно предположить, что существует счетное число переменных.

Представим переменные в двоичной кодировке как 01, 011, 0111, 01111 и т.д. Предположим, что 01 всегда является стартовым символом. Кроме того, в этой кодировке терминал 0 будет представляться как 00, а терминал 1 как 001. Символ « » представляется как 0011, а запятая как 00111. Любая грамматика с терминалами 0 и 1 может быть представлена строкой правил, использующей стрелку (0011) для разделения левой и правой частей, и запятой (00111) для разделения правил. Строки, представляющие символы, используемые в правилах, - это 00, 001 и 01ⁱ для i = 1, 2, ... Множество используемых переменных определяется неявно правилами.

Отметим, что не все строки из 0 и 1 представляют грамматики, и не обязательно КЗГ. Однако, по данной строке легко можно сказать, представляет ли она КЗГ. i- ю грамматику можно найти, генерируя двоичные строки в описанном порядке пока не сгенерируется i-я строка, являющаяся КЗГ. Поскольку имеется бесконечное число КЗГ, их можно занумеровать в некотором порядке G₁, G₂, ...

Определим L = {x_i|x_i L(G_i)}. L рекурсивно. По строке x_i легко можно определить i и затем определить G_i. По теореме 2.6. имеется алгоритм, определяющий для x_i принадлежит ли он L(G_i), поскольку G_i КЗГ. Таким образом имеется алгоритм для определения для любого x принадлежит ли он G.

Покажем теперь, что L не генерируется никакой КЗ-грамматикой. Предположим, что L генерируется КЗ- грамматикой G_i. Во-первых, предположим, что . Поскольку . Но тогда по определению xi L(G_i) - противоречие. Таким образом предположим, что x_i L. Поскольку L(G_i) = L, x_i L(G_i). Но тогда по определению - снова противоречие. Из чего можно заключить, что L не генерируется G_i. Поскольку приведенный выше аргумент справедлив для каждой КЗ- грамматики G_i в перечислении, и поскольку перечисление содержит все КЗ-грамматики, можно заключить, что L не КЗ-язык. Поэтому L - рекурсивное множество, не являющееся контекстно-зависимым.