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

2020-06-032021-03-09zzyxelСтудИзба

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

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

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

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

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

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

Пример 2.1. Для цепочки abbba префиксом является любая цепочка из множества $L_1 = {e, a, ab, abb, abbb, abbba}$ суффиксом является любая цепочка из множества {e, a, ba, bba, bbba, abbba} подцепочкой является любая цепочка из множества L_1 bigcup L_2

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

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

$L_1={O}$ — пустой язык;
$L_2 = {e}$ - язык, содержащий только пустую цепочку (заметим, что и - различные языки)
- язык, содержащий цепочки из a и b, длина которых не превосходит 2
- язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b
$L_5 = {a^{n^2}|n>0}$ - язык цепочек из a, длины которых представляют собой квадраты натуральных чисел.

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

Программирование графических приложений (ПГП)

Ознакомительная Практика (ОП1) Вариант Н26

Объектно-ориентированное программирование (ООП)

500 250 руб.

Лабораторная работа L36 (№7) отчет+код Вариант 36(?)

Объектно-ориентированное программирование (ООП)

150 руб.

Практика ООП Берчун РК6

Объектно-ориентированное программирование (ООП)

499 руб.

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

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

Пример 2.3. Пусть V={0,1} . Тогда $V^*={e, 0, 1, 00, 01, 10, 11, 000, ldots}, V^+={0, 1, 00, 01, 10, 11, 000, ldots}$

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

Пусть L_1 и L_2 - языки в алфавите V . Конкатенацией языков L_1 и L_2 называется язык $L_1L_2 = {xy|x in L_1, y in L_2}$ .

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

$L^0={\|e}$	(1)
$L^n = LL^{n-1}, n geq1$	(2)

$L^*=bigcuplimits^infty_{n=0} L^n$

(3)

Пример 2.4. Пусть $L_1 = {aa, bb}$ и $L_2 = {e, a, bb}$ . Тогда

$L_1L_2={aa, bb, aaa, bba, aabb, bbbb}$ , и

$L^*_1={e, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, ldots}$

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

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

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

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

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

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

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

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

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

Предположим, что V имеет p символов. Мы можем рассматривать цепочки из V^* как числа, представленные в базисе p, плюс пустая цепочка e. Можно занумеровать цепочки в порядке возрастания длины и в "числовом" порядке для цепочек одинаковой длины. Такая нумерация для цепочек языка ${a; b; c}^*$ приведена на рис. 2.1, а.

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

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

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

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

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 - алфавит терминальных символов, N cap T = {O}

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

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

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

Будем использовать также сокращенную запись A rightarrow alpha_1|alpha_2|ldots|alpha_n для обозначения группы правил Arightarrowalpha_1,Arightarrowalpha_2,ldots,Arightarrowalpha_n.

Определим на множестве (N cup T)^* бинарное отношение выводимости Rightarrow следующим образом: если delta rightarrow gamma in P , то alpha delta beta Rightarrow alpha gamma beta для всех alpha, beta in (N cup T)^* . Если alpha_1 Rightarrow alpha_2 , то говорят, что цепочка alpha_2 непосредственно выводима из alpha_1 .

Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения Rightarrow , а также его степень k geq 0 (обозначаемые соответственно Rightarrow^* , Rightarrow^+ и Rightarrow^k ). Если alpha_1Rightarrow^*alpha_2(alpha_1Rightarrow^+alpha_2, alpha_1Rightarrow^k alpha_2) , то говорят, что цепочка alpha_2 выводима (нетривиально выводима, выводима за k шагов) из alpha_1 .

Если alphaRightarrow^k beta(k geq 0) , то существует последовательность шагов

$gamma_0 Rightarrow gamma_1 Rightarrow gamma_2 Rightarrow ldots Rightarrow gamma_{k-1} Rightarrow gamma_k$

где alpha ; = ; gamma_0 и beta; = ;gamma_k . Последовательность цепочек gamma_0, gamma_1, gamma_2, ldots, gamma_k в этом случае называют выводом beta из alpha

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

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

$L(G);=; {omegamidomegain T^*, SRightarrow^+omega}$

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

Пример 2.5. Грамматика G = ({S, B, C}, {a, b, c}, P, S), где P = {S rightarrow aSBC, ; S rightarrow aBC,; CB rightarrow BC, ; aB rightarrow ab,; bB rightarrow bb,; bC rightarrow bc, ; cC rightarrow cc} , порождает язык $L(G) = {a^nb^nc^nmid n>0}$

Действительно, применяем n - 1 раз правило 1 и получаем $a^{n-1}S(BC)^{n-1}$ , затем один раз правило 2 и получаем a^n(BC)^n , затем n(n - 1)/2 раз правило 3 и получаем a^nB^nC^n .

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

Пример 2.6. Рассмотрим грамматику G ;= ; ({S},{0,1},{S rightarrow 0S1,;Srightarrow01},S) . Легко видеть, что цепочка 000111 in L(G) , так как существует вывод

S Rightarrow 0S1 Rightarrow 00S11 Rightarrow 000111

Нетрудно показать, что грамматика порождает язык $L(G); = ; {0^n1^n mid n>0}$ .

Пример 2.7. Рассмотрим грамматику G ;= ; ({S,A},{0,1},{Srightarrow 0S, ; S rightarrow 0A, ; A rightarrow 1A, ; A rightarrow 1}, ; S) . Нетрудно показать, что грамматика порождает язык $L(G)={0^n1^mmid n, ;m>0}$

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

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

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

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

(2) если

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

(3) если каждое правило грамматики имеет вид A rightarrow beta , где A in N, beta in (N cup T)^* , то ее называют грамматикой типа 2, или контекстно-свободной (КС-грамматикой).

(4) если каждое правило грамматики имеет вид либо A rightarrow xB , либо , где A, B in N, x in T^* то ее называют грамматикой типа 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') следующим образом:

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

Arightarrowalpha_0 X_1 alpha_1 ldots X_k alpha_k

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

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

Шаг 1. Строим множество $N_0={N mid Nrightarrow e}$

Шаг 2. Строим множество $N_i=N_{i-1}cup {N mid Nrightarrow alpha, ; alpha in {N_{i-1}}^*}$

Шаг 3. Если $N_i=N_{i-1}$ , перейти к шагу 4, иначе шаг 2.

Шаг 4. Если S in N_i , значит S rightarrow^* e .

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

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

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

Пример 2.8. Рассмотрим грамматику G = ({S, A, B}, {0, 1}, {S rightarrow AB, ; A rightarrow 0A, ; A rightarrow 0, ; B rightarrow 1B, ; B rightarrow 1}, ; S) . Эта грамматика является контекстно-свободной. Легко показать, что $L(G) = {0^n 1^m mid n,m ; > ; 0}$ . Однако, в примере 2.7 приведена праволинейная грамматика, порождающая тот же язык.

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

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

${{a,b}^*backslash a^n b^m a^n b^m mid n,m geq1}$

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

Однако воодушевл_нных построением в рамках КС- грамматики цепочек вида ${a^n b^m a^n b^m }$ (здесь и далее в этом примере n, m, k, l, j ; geq ; 1) ждет некоторое разочарование. Действительно, в отличие от таких случаев, как ${a^n b^n a^m b^m }$ , ${a^n b^m a^m b^n }$ , ${a^n b^m b^n a^m}$ и т.п., обе зависимости (по n и по m) придется отслеживать одновременно и из двух разных центров порождения, к чему КС-грамматики по своей природе (виду своих правил) оказываются не предназначены.

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

${a^n}, {b^n}, {a^n b^m}, {b^n a^m}, {a^n b^m a^k}, {b^n a^m b^k}ldots$

Однако бесконечно продолжать в духе ${b^n a^m b^k a^l b^j}$ уже как- то скучно. Замечаем, что $b{a, b}^*$ вполне конечным образом определяет половину из упомянутых бесчисленных описаний, а в следующий момент симметрия нам подсказывает и язык ${a, b}^*a$ .

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

${a^n b^m}, ; b{a,b}^*, ; {a,b}^*a$

Далее рассмотрим случай ${a^n b^m a^k b^l mid n neq k ; или ; m neq l}$ . Но что такое, к примеру, n neq k ? То же самое, что объединение условий n>k ; и ; n<k ! И здесь перешли к конструктиву, который несложно строится в рамках КС-грамматики.

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

${a^n b^m a^k b^l}a{a,b}^*$

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

Так, если язык ${a^n b^m }$ может быть порожден грамматикой

S_1rightarrow AB

Arightarrow aA mid a

Brightarrow bB mid b

а язык $b {a, b}^*$ - грамматикой

S_2 rightarrow bC

C rightarrow CC mid a mid b mid varepsilon ,

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

S rightarrow S_1 mid S_2

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

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

varphi A psi rightarrow varphietapsi, ; (mid eta mid geq 1)

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

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

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

${a^{n^2} mid ngeq 0}$ , порождающего слова вида varepsilon, ; a, ; a^4, ; a^9, ;ldots

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

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

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

Правила	Вид получаемой цепочки

	$C^{n-1} ; DCAD^{n-1}$ (A задерживает C)
	(отработали все C)

Получили $a^{n^2}$ , но что делать с C и D? Сделав свое дело, они стали лишними.

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

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

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

Правила	Вид получаемой цепочки


	$BC^{n-1}; (DA)^n ; CE$ (C прошло первый раз)
	(прошли все C)
	$BA^n ; (DA^n)^{n-1} ; C^n ; E$
	$A^{n*n}BC^n E$ (ушли все D)
	$A^{n*n}BE$ (ушли все C)
	$A^{n*n}$ (ушли B c E)
	$a^{n*n}$

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

Снова:

Правила	Вид получаемой цепочки


	$BC^{n-1}; (DA)^n ; CE$ (C прошло первое C)
	(прошли все C)
	$a^ BA^n ; (DA^n)^{n-1} ; C^n ; E$
	(ушли все D)
	$(a^2 A^n)^n BEa^{2n}$ (ушли все C)
	$a^{n*n+2n}BEa^{2n}$ (ушли B c E)
	$a^{{n^2}+4n+4}=a^{(n+2)^2}$

Итак, если сокращать нельзя, достраиваем слово до ближайшего подходящего квадрата. В данном случае удобнее достроить слово до $a^{(n+2)^2}$ , т.к. для достройки до $a^{(n+1)^2}$ нам бы потребовалось перевести BE rightarrow! a , т.е. опять что-то сократить. Напомним, что в КЗ-грамматиках допускается переход аксиомы в пустую цепочку ( varepsilon ), если аксиома нигде более не встречается в правых частях правил (т.е. когда из начального ничего получают другое ничего).

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

AB rightarrow A'B rightarrow A'B' rightarrow BB' rightarrow BA

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

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

AB rightarrow A'B rightarrow A'B' rightarrow A'A rightarrow BA

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

x=Aunderline{AB}B xrightarrow[]{*} AA'underline{AB} xrightarrow[]{*} Aunderline{A'B}A xrightarrow[]{*} ABAA=y

(mid ! x ! mid _A = mid ! x ! mid _B = 2, quad amid ! y ! mid _A = 3 ; и mid ! y ! mid _B=1 )!

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

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

Правила	Вид получаемой цепочки
	BSE
	BCⁿDⁿ E
	BC^n-1DCAD^n-1E
	BC^n-1(DA)ⁿCE
	B(DAⁿ)ⁿCⁿE
	a²BAⁿ(DAⁿ)^n-1CⁿE
	(a²Aⁿ)ⁿBCⁿE
	(a²Aⁿ)ⁿBEa²ⁿ
	a^n*n+2nBEa²ⁿ
$BE xrightarrow[]{*} a^4$	$a^{n^2 +4n+4}= a^{(n+2)^2}$

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

Формально машина Тьюринга (Tm) - это Tm =
(Q, Gamma, Sigma, D, q_0, F) , где

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

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

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

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

D функция переходов, отображение из (Q - F)times Gamma rightarrow Q times Gammatimes {L,R}; для некоторых аргументов функция D может быть не определена.

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

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

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

Так определенная машина Тьюринга называется детерминированной. Недетерминированная машина Тьюринга для каждой пары (Q - F)times Gamma может иметь несколько возможных переходов. В начале n ячеек ленты содержат вход $w in (Gamma -{B})^*$ , остальная часть ленты содержит пустые символы. Обозначим конфигурацию машины Тьюринга как (q, w, i) , где q in Q - текущее состояние, i - выделенный элемент строки, "положение головки" , w - текущее содержимое занятого участка ленты. Если головка сдвигается с ячейки, машина должна записать в нее символ, так что лента всегда состоит из участка, состоящего из конечного числа непустых символов и бесконечного количества пустых символов.

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

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

где 1 leq i leq n+1 .

Если 1 leq i leq n и D(q, A_i) = (p, A, R)

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

$(q, ;A_1A_2ldots A_n,i)vdash_{Tm} ; (p, ; A_1A_2 ldots A_{i-1}AA_{i+1}ldots A_n, ; i+1)$

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

Если 2 leq i leq n и D(q, A_i) = (p, A, L)

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

$(q, ;A_1A_2ldots A_n,i)vdash_{Tm} ; (p, ; A_1A_2 ldots A_{i-1}AA_{i+1}ldots A_n, ; i-1)$

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

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

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

$(q, ;A_1A_2ldots A_n,n+1)vdash_{Tm} ; (p, ; A_1A_2 ldots A_n A, n+2)$

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

$(q, ; A_1A_2 ldots A_n,n+1)vdash_{Tm} ; (p, ; A_1A_2 ldots A_n A, n)$

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

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

$L={w! mid ! w in Sigma^* ; и ; (q_0,w,1)vdash_{Tm*}(q,u,i) ; для ; некоторых ; q in F, u in Gamma^* ; и ; целого ; i}$

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

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

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

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

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

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

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

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

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

Если дано слово x, T перечисляет слова x₁, x₂... пока не будет x_i = x.
T генерирует кодировку машины Тьюринга T_i.
Управление передается гипотетической машине, которая определяет останавливается ли T_i на входе x_i.
Если выясняется, что T_i не останавливается на входе x_i, то T останавливается и допускает x_i.
Если выясняется, что 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 - рекурсивное множество, L subseteq T^* , то существует 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. Пусть x_1, x_2, ldots - нумерация всех слов некоторого конечного алфавита - и T₁, T₂, ... - нумерация всех машин Тьюринга с ленточными символами, выбранными из некоторого конечного алфавита, включающего -. Пусть $L_2 = {x_i mid x_i$ допускается T_i} . L₂ - рекурсивно перечислимое множество, дополнение которого не рекурсивно перечислимо.

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

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

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

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

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

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

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

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

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

Tm = (Q, Sigma, Gamma, D, q_0, F)

где Gamma=Т cup Sigma cup {B,sharp,X}

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

Вначале Tm содержит на входной ленте w in Sigma^* . 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 печатает на ленте строку вида sharp w sharp y sharp , y in V^* в точности, если $S Rightarrow _{G*y}$ . Если y = w, Tm допускает L.

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

Доказательство. Пусть Tm = (Q, Sigma, Gamma, D, q_0, F) допускает L. Построим грамматику G, которая недерминированно генерирует две копии представления некоторого слова из Sigma^* и затем симулирует поведение Tm на одной из копий. Если Tm допускает слово, то G трансформирует вторую копию в терминальную строку. Если Tm не допускает L, то вывод никогда не приводит к терминальной строке.

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

G=(N, Sigma, P, A_1) , где $N=([Sigma cup {e}]times Gamma)cup Q cup {A_1,A_2,A_3}$

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

для каждого
для каждого и каждого и такого, что
для каждого C, J, I из , a и b
для каждого

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

A_1Rightarrow^* ; q_0[a_1, ; a_1][a_2, ; a_2]ldots [a_n, ; a_n]A_2

где a_i in Sigma для некоторого

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

A_1Rightarrow^* ; q_0[a_1, ; a_1][a_2, ; a_2]ldots [a_n, ; a_n][e, ; B]^m

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

$(q_0, ; a_1a_2 ldots a_n, ;1)vdash_{Tm*} ; (q, ; X_1 X_2 ldots X_S, ; r)$ , то

$q_0[a_1,a_1][a_2,a_2] ldots [a_n,a_n][e,B]^m Rightarrow_{G*}$

$Rightarrow_{G*} [a_1,X_1][a_2,X_2] ldots [a_{r-1},X_{r-1}]q[a_r,X_r] ldots [a_{n+m},X_{n+m}]$

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

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

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

$begin{multline}
(q_0,a_1 a_2 ldots a_n , ; 1)vdash_{Tm*}notag \
vdash_{Tm*} ; (q_1,X_1X_2 ldots X_r,j_1)vdash_{Tm*} notag \
vdash_{Tm*}(q_2,Y_1Y_2 ldots Y_S,j_2)
end{multline}$

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

$begin{multline}
q_0[a_1, a_1 ][a_2,a_2] ldots [a_n,a_n][e,B]^m Rightarrow_{G^*}notag \
Rightarrow_{G^*}[a_1,X_1][a_2,X_2] ldots [a_{r-1},X_{r-1}]q_1[a_{j1},X_{j1}]ldots notag \
ldots [a_{n+m},X_{n+m}]
end{multline}$

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

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

$q_1[a_{j1},X_{j1}]rightarrow [a_{j1},Y_{j1}]q_2 ; или$

$[ a_{j1-1},X_{j1-1} ] q_1[a_{j1},X_{j1}] rightarrow q_2[a_{j1-1},X_{j1-1}][a_{j1},Y_{j1}]$

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

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

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

$begin{multline}
q_0[a_1,a_1][a_2,a_2] ldots [a_n,a_n][e,B]^m Rightarrow^{G*} notag \
Rightarrow^{G*} ; [a_1,Y_1]q_2[a_{j2},Y_{j2}] ldots [a_{n+m},Y_{n+m}]
end{multline}$

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

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

$[a_1,X_1] ldots q[a_j,X_j] ldots [a_{n+m},X_{n+m}]Rightarrow^* a_1 a_2 ldots a_n.$

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

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

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

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

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

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

Определим множество Tm как множество строк u in (N cup T)^+ длины не более n таких, что вывод S Rightarrow^* ; u имеет не более m шагов. Ясно, что T₀ = {S}.

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

$T_m=T_{m-1} cup {u mid v Rightarrow для ; некоторого ; v in T_{m-1}, ;где mid ! u ! mid leq n }$

Если SRightarrow^* ; u и mid !u ! mid leq n, ; то ; u in T_m для некоторого m. Если из S не выводится u или |u| > n, то u не принадлежит T_m ни для какого m.

Очевидно, что $T_m subseteq T_{m-1}$ для всех 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. Если w in T_m, то S Rightarrow^* w .

Покажем, что существует такое m, что T_m = Tm-1. Поскольку для каждого i > 1 справедливо $T_i supseteq T_{i-1}$ , то если $T_i neq T_{i-1}$ , то число элементов в T_i по крайней мере на 1 больше, чем в T_i-1. Пусть mid ! N cup T ! mid = k . Тогда число строк в ( N cup T )^+ длины меньшей или равной n равно k+k^2+ ldots +k^n leq nk^n . Только эти строки могут быть в любом T_i. Значит, T_m = T_m-1 для некоторого m leq nk^n . Таким образом, процедура, вычисляющая T_i для всех i geq 1 до тех пор, пока не будут найдены два равных множества, гарантированно заканчивается, значит, это алгоритм.

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

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

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

(q,A₁A₂,...,A_n,i) где q in Q, ; A_1,A_2, ldots ,A_n in Gamma, i -целое от 1 до n. Предположим, что (p,A,L) in D(q,A_i) и i > 1

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

$(q,A_1,A_2 ldots A_n,i)vdash_M (p,A_1,A_2 ldots A_{i-1}AA_{i+1} ldots A_n,i-1)$

(p,A,R) in D(q,A_i) и i < n, будем говорить, что

$(q,A_1,A_2 ldots A_n,i)vdash_M (p,A_1,A_2 ldots A_{i-1}AA_{i+1} ldots A_n,i+1)$

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

(q, alpha , i )vdash *_M (q, alpha , i ) и

Если (q_1, alpha_1 , i_1 )vdash *_M (q_2, alpha_2 , i_2 ) и (q_2, alpha_2 , i_2 )vdash *_M (q_3, alpha_3 , i_3 ) ,

то (q_1, alpha_1 , i_1 )vdash *_M (q_3, alpha_3 , i_3 )

Язык, допускаемый M - это ${w mid w in (Sigma { copyright, $ })^*$ и (q_0,copyright w $, 1) vdash * (q, alpha , i) для некоторого q in F, alpha in Gamma^* и целого i}.

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

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

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

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

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

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

Если x ; in ; L(G) , то существует некоторая последовательность шагов, на которой ЛОА строит 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. Во-первых, предположим, что x_i in L . Поскольку L(G_i) = L, x_i in 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 - рекурсивное множество, не являющееся контекстно-зависимым.

Поделитесь ссылкой:

Популярные услуги

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

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

Рекомендуемые лекции