В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 6
Текст из файла (страница 6)
Этопротиворечит утверждению, что ∼L2 — это язык, допускаемый Tj .24Глава 2. Языки и их представлениеТеорема 2.3. Существует рекурсивно перечислимое множество, не являющееся рекурсивным.Д о к а з а т е л ь с т в о . По лемме 2.2 L2 — рекурсивно перечислимоемножество, дополнение которого не рекурсивно перечислимо. Если бы L2было рекурсивно, то по лемме 2.1 ∼L2 было бы рекурсивно и, следовательно,рекурсивно перечислимо, что противоречит утверждению леммы 2.2.2.5.
Связь машин Тьюринга и грамматик типа 0Докажем, что язык распознаётся машиной Тьюринга, если и только еслион генерируется грамматикой типа 0. Для доказательства части «если» мыпостроим недетерминированную машину Тьюринга, которая будет недетерминированно выбирать выводы в грамматике и смотреть, является ли выводвходом. Если да, то машина допускает вход.Для доказательства части «только если» мы построим грамматику, которая недетерминированно генерирует представления терминальной строкии затем симулирует машину Тьюринга на этой строке.
Если строка допускается некоторой M , то строка конвертируется в терминальные символы, которыеона представляет.Теорема 2.4. Если L генерируется грамматикой типа 0, то L распознаётся машиной Тьюринга.Д о к а з а т е л ь с т в о . Пусть G = (N , Σ, P , S) — грамматика типа 0и L = L(G). Опишем неформально недетерминированную машину ТьюрингаM , допускающую L:M = (Q, Σ, Γ, D, q0 , F )где Γ = N ∪ Σ ∪ {B , #, X}.Предполагается, что последние три символа не входят в N ∪ Σ.Вначале M содержит на входной ленте w ∈ Σ∗ . Затем M вставляет #перед w, сдвигая все символы w на одну ячейку вправо, и #S# после w, такчто содержимым ленты становится #w#S#.Теперь M недетерминированно симулирует вывод в G, начиная с S . Каждая сентенциальная форма вывода появляется по порядку между последнимидвумя #.
Если некоторый выбор переходов ведет к терминальной строке,то она сравнивается с w. Если они совпадают, то M допускает.Формально, пусть M имеет на ленте #w#A1 A2 . . . Ak #. M передвигаетнедетерминированно головку по A1 A2 . . . Ak , выбирая позицию i и константуr между 1 и максимальной длиной левой части любого правила вывода в P .Затем M проверяет подстроки Ai Ai+1 . . .
Ai+r−1 . Если Ai Ai+1 . . . Ai+r−1 —левая часть некоторого правила вывода из P , то она может быть замененана правую часть. Тогда M может сдвинуть Ai+r Ai+r+1 . . . Ak # либо влево,2.5. Связь машин Тьюринга и грамматик типа 025либо вправо, освобождая или заполняя место, если правая часть имеет длину,отличную от r.Из этой простой симуляции выводов в G видно, что M печатает на лентестроку вида #w#y#, y ∈ V ∗ , в точности, если S ⇒ G∗ y .
Если y = w, то Mдопускает L.Теорема 2.5. Если L распознаётся некоторой (детерминированной)машиной Тьюринга, то L генерируется грамматикой типа 0.Д о к а з а т е л ь с т в о . Пусть M = (Q, Σ, Γ, D, q0 , F ) допускает L. Построим грамматику G, которая недерминированно генерирует две копии представления некоторого слова из Σ∗ и затем симулирует поведение M наодной из копий. Если M допускает слово, то G трансформирует вторуюкопию в терминальную строку. Если M не допускает L, то вывод никогдане приводит к терминальной строке.Формально, пустьG = (N , Σ, P , A1 ), где N = ([Σ ∪ {e}] × Γ), ∪Q ∪ {A1 , A2 , A3 },и P состоит из следующих правил.1.
A1 → q0 A2 .2. A2 → [a, a]A2 для каждого a ∈ Σ.3. A2 → A3 .4. A3 → [e, B]A3 .5. A3 → e.6. q[a, C] → [a, E]p для каждого a ∈ Σ ∪ {e} и каждого q ∈ Q и такогоC ∈ Γ, что D(q , C) = (p, E , R).7. [b, I]q[a, C] → p[b, I][a, J] для каждых C , J , I из Γ, a и b из Σ ∪ {e}и таких q из Q, что D(q , C) = (p, J , L).8. [a, C]q → qaq , q[a, C] → qaq , q → e для каждых a ∈ Σ ∪ {e}, C ∈ Γ, q ∈ F.Используя правила 1 и 2, получаемA1 ⇒ ∗ q0 [a1 , a1 ][a2 , a2 ] . . . [an , an ]A2 ,где ai ∈ Σ для некоторого i.Предположим, что M допускает строку a1 a2 . . .
an . Тогда найдется m, длякоторого M использует не более, чем m ячеек справа от входа. Используяправило 3, затем m раз правило 4 и, наконец, правило 5, имеемA1 ⇒ ∗ q0 [a1 , a1 ][a2 , a2 ] . . . [an , an ][e, B]m .Начиная с этого момента могут быть использованы только правила 6и 7, пока не сгенерируется допускающее состояние. Отметим, что первыекомпоненты ленточных символов в (Σ ∪ {e}) × Γ никогда не меняются. Индукцией по числу шагов M можно показать, что если(q0 , a1 a2 . . .
an , 1) |− ∗M (q , X1 X2 . . . Xs , r),26Глава 2. Языки и их представлениетоq0 [a1 , a1 ][a2 , a2 ] . . . [an , an ][e, B]m ⇒ ∗G⇒ ∗G [a1 , X1 ][a2 , X2 ] . . . [ar−1 , Xr−1 ]q[ar , Xr ] . . . [an+m , Xn+m ],где a1 , a2 , . . . an принадлежат Σ, an+1 = an+2 = . . . an+m = e, X1 , X2 ,. .
.Xn+mпринадлежат Γ и Xs+1 =Xs+2 = . . .Xn+m =B .Предположение индукции тривиально для 0 шагов. Предположим, что оносправедливо для k − 1 шагов. Пусть(q0 , a1 a2 . . . an , 1) ⊢∗M (q1 , X1 X2 . . . Xr , j1 ) ⊢M (q2 , Y1 Y2 . . . Ys , j2 )за k шагов. По предположению индукцииq0 [a1 , a1 ][a2 , a2 ] . . .
[an , an ][e, B]m ⇒ ∗G⇒ ∗G [a1 , X1 ][a2 , X2 ] . . . [ar−1 , Xr−1 ]q1 [aj1 , Xj1 ] . . . [an+m , Xn+m ].Пусть E = L, если j2 = j1 − 1, и E = R, если j2 = j1 + 1. В этом случаеD(q1 , Xj1 ) = (q2 , Yj1 , E).По правилу 6 или 7q1 [aj1 , Xj1 ] → [aj1 , Yj1 ]q2или[aj1 −1 , Xj1 −1 ]q1 [aj1 , Xj1 ] → q2 [aj1 −1 , Xj1 −1 ][aj1 , Yj1 ],в зависимости от того, равно ли E значению R или L. Теперь Xi = Yi длявсех i 6= j1 .Таким образом,q0 [a1 , a1 ][a2 , a2 ] . . .
[an , an ][e, B]m ⇒ ∗G [a1 , Y1 ]q2 [aj2 , Yj2 ] . . . [an+m , Yn+m ],что доказывается предположением индукции.По правилу 8, если q ∈ F , легко показать, что[a1 , X1 ] . . . q[aj , Xj ] . . . [an+m , Xn+m ] ⇒ ∗ a1 a2 . . . an .Таким образом, G может генерировать a1 a2 . . . an , если a1 a2 . . . an допускается M . Таким образом, L(G) включает все слова, допускаемые M .Для завершения доказательства необходимо показать, что все слова из L(G)допускаются M . Индукцией доказывается, что A1 ⇒ ∗G w, только если wдопускается M .Тем самым мы доказали, что если слово допускается M , то оно порождается G. Если слово не допускается, то M не попадает в заключительноесостояние и слово не порождается.2.6. Связь линейно ограниченных автоматов и КЗ-языков272.6.
Линейно ограниченные автоматыи их связь с контекстно-зависимыми грамматикамиКаждый КЗ-язык является рекурсивным, но обратное не верно. Покажем,что существует алгоритм, позволяющий для произвольного КЗ-языка L в алфавите T и произвольной цепочки w ∈ T ∗ определить, принадлежит ли wязыку L.Теорема 2.6. Каждый контекстно-зависимый язык является рекурсивным языком.Д о к а з а т е л ь с т в о . Пусть L — контекстно-зависимый язык. Тогдасуществует некоторая неукорачивающая грамматика G = (N , T , P , S), порождающая L.Пусть w ∈ T ∗ и |w| = n.
Если n = 0, т. е. w = e, то принадлежность w ∈ Lпроверяется тривиальным образом. Так что будем предполагать, что n > 0.Определим множество Tm как множество строк u ∈ (N ∪ T )+ длиныне более n, таких, что вывод S ⇒ ∗ u имеет не более m шагов. Ясно, чтоT0 = {S}.Легко показать, что Tm можно получить из Tm−1 , просматривая, какиестроки с длиной, меньшей или равной n, можно вывести из строк из Tm−1применением одного правила, т.
е.Tm = Tm−1 ∪ {u | v ⇒ u для некоторого v ∈ Tm−1 , где |u| 6 n}.Если S ⇒ ∗ u и |u| 6 n, то u ∈ Tm для некоторого m. Если из S не выводится u или |u| > n, то u не принадлежит Tm ни для какого m.Очевидно, что Tm ⊇ Tm−1 для всех m > 1. Поскольку Tm зависит толькоот Tm−1 , то из Tm = Tm−1 следует Tm = Tm+1 = Tm+2 = .
. . . Процедура будетвычислять T1 , T2 , T3 , . . .пока для некоторого m не окажется Tm = Tm−1 . Еслиw не принадлежит Tm , то w не принадлежит и L(G), поскольку для j > mвыполняется Tj = Tm . Если w ∈ Tm , то S ⇒ ∗ w.Покажем, что существует такое m, что Tm = Tm−1 . Поскольку для каждого i > 1 справедливо Ti ⊇ Ti−1 , то из Ti 6= Ti−1 следует, что число элементов в Ti по крайней мере на 1 больше, чем в Ti−1 . Пусть |N ∪ T | = k .Тогда число строк в (N ∪ T )+ длиной, меньшей или равной n, равноk + k 2 + .
. . + k n 6 nk n . Только эти строки могут быть в любом Ti . Значит,Tm = Tm−1 для некоторого m 6 nk n . Таким образом, процедура, вычисляющая Ti для всех i > 1 до тех пор, пока не будут найдены два равныхмножества, гарантированно заканчивается; значит, это алгоритм.Линейно ограниченный автомат (ЛОА) — это недетерминированнаямашина Тьюринга с одной лентой, которая никогда не выходит за пределы |w|ячеек, где w — вход. Формально линейно ограниченный автомат обозначается28Глава 2. Языки и их представлениеM = (Q, Σ, Γ, D, q0 , F ). Обозначения имеют тот же смысл, что и для машинТьюринга: Q — это множество состояний, F ⊆ Q — множество заключительных состояний, Γ — множество ленточных символов, Σ ⊆ Γ — множествовходных символов, q0 ∈ Q — начальное состояние, D — отображение из Q × Γв подмножество Q × Γ × {L, R}.Множество Σ содержит два специальных символа, обычно обозначаемыеc и $, — левый и правый концевые маркеры соответственно.
Эти символы°располагаются сначала по концам входа, и их функция — предотвратитьпереход головки за пределы области, в которой расположен вход.Конфигурация M и отношение |−M , связывающее две конфигурации, есливторая может быть получена из первой применением D, определяются так же,как и для машин Тьюринга. Конфигурация M обозначается как (q , A1 , A2 , . . .. . . , An , i), где q ∈ Q, A1 , A2 , . . . , An ∈ Γ, i — целое от 1 до n. Предположим,что (p, A, L) ∈ D(q , Ai ) и i > 1. Будем говорить, что(q , A1 , A2 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
