Лекции Русакова (1021002), страница 14
Текст из файла (страница 14)
Перед началом работы n ячеек лентысодержат символы входной цепочки αi = xi1 , xi2 ,..., xin, все остальные ячейкисчитаются заполненными специальным символом В («пустое место»),который не является входным (рис. 4.10).131Рис. 4.10. Интерпретация машины ТьюрингаОпределение.Формально машина Тьюринга определяется как следующая шестёрка:Т = (V1, V2, Q, δ, q0, F),где V1 = {a1, ..., an} – входной алфавит (конечное множество символов);V2 = {А1, ..., Аk, B} – конечное множество ленточных символов,которое в качестве своего подмножества содержит входной алфавит;Q = {q0 , q1, ..., qn-1} – конечное множество состояний;q0 ∈ Q – начальное состояние;F ⊆ Q – множество заключительных состояний;δ – функция, отображающая Q .
V2 в Q . V2 – {B} . {Л, П}.(Л и П – специальные символы, указывающие на направлениедвижения головки, лево и право).Отображение (функцию) δ удобно задавать совокупностью командвида: (q, A) → (q′, A′, Л) либо (q, A) → (q′, A′, П).Определение.Ситуация машины Тьюринга Т – это тройка вида (q, β, i),где q ∈ Q;132β = A1, ..., An – часть ленты, не содержащая символов В (непустая частьленты);i = (0 ≤ i ≤ n+1) – расстояние ленточной (пишущей - читающей) головкиот левого конца β; при i = 0 головка находится левее самого левогосимвола β, при i = n+1 – правее самого правого.Рассмотрим произвольную ситуацию машины Т:(q, A1 ...
Ai .... An, i), 1 ≤ i ≤ n.Пусть среди команд отображения δ имеется следующая:(q, Ai) → (q′, X, Л).При этом возможно следующее движение (или элементарное действие)машины Тьюринга: головка стирает символ Аi, записывает вместо негосимвол Х и перемещается на одну ячейку влево.Между старой и вновь возникшей ситуациями в этом случаесуществует отношение, которое записывается следующим образом:(q, A1 ... Ai ....
An, i) ├ (q′, A1 ... Ai-1 Х Ai+1.... An, i -1).Символ ├ означает – «утверждается».Аналогично для команды (q, Ai) → (q′, X, П) движение машиныТьюринга записывается как(q, A1 ... Ai .... An, i) ├ (q′, A1 ... Ai-1 Х Ai+1.... An, i+1).Кроме рассмотренной ситуации возможны и такие:(q, A1 ... An, 0);(q, A1 ... An, n+1).К ним применимы команды вида:(q, В) → (q′, X, Л) либо133(q, В) → (q′, X, П).Первая из этих команд меняет указанные ситуации соответственноследующим образом:(q, A1 ... An, 0) ├ (q′, X A1 ... An, 0);(q, A1 ...
An, n+1) ├ (q′, A1 ... An X, n).Вторая из этих команд меняет их так:(q, A1 ... An, 0) ├ (q′, X A1 ... An, 2);(q, A1 ... An, n+1) ├ (q′, A1 ... An X, n+2).Определение.Если ситуации (q1, β1, i1) и (q2, β2, i2) связаны между собой некоторымчислом элементарных действий, то между ними имеет место отношение:(q1, β1, i1) ├* (q2, β2, i2).Определение.Язык, допускаемый машиной Тьюринга Т, это:L(Т) = {α | α∈ V1* ∧ (q0, α, 1) ├* (qf, β, i)},где qf = F, β ∈ V2*, i ≥ 0.Другими словами, если, преобразуя входную цепочку α, машина Токажется в одном из своих заключительных состояний, эта цепочкадопускается данной машиной.Определение.Так же как для автоматов введем понятие недетерминированноймашины Тьюринга.
Её отличие от детерминированной заключается в том, чтофункция δ отображает множество Q x V2 в множество подмножествQ x (V2 – {B}) x {Л, П}.134Определение.Если язык L порождается грамматикой типа 0, то L допускаетсянекоторой машиной Тьюринга. Верно и обратное, если язык L допускаетсянекоторой машиной Тьюринга, то L порождается грамматикой типа 0.4.07. МашиныТьюрингаилинейно-ограниченныеавтоматы.Рассмотренные типы автоматов и машин Тьюринга часто используютсядля построения автоматно-лингвистических моделей, предназначенных дляраспознавания языков. Необходимо знать, разрешима ли для них такназываемая проблема распознавания или нет.Определение.Проблема разрешимости заключается в следующем.
Пусть естьнекоторая цепочка α на входе машины Тьюринга, которая допускает язык L.Всегда ли можно установить принадлежность цепочки α к языку L законечное число элементарных действий этой машины?Однако не для всех языков типа 0 эта проблема разрешима.Другими словами, можно подобрать такой язык типа 0, чтосоответствующая ему машина Тьюринга для некоторой цепочки α законечноечислоэлементарныхдействийнесможетустановитьпринадлежность ее к данному языку. Поэтому машина Тьюринга в общемвиде не нашла применения в реальных кибернетических моделях; языкитипа 0 также не используются.135Наибольший интерес представляют различные специальные классымашин Тьюринга, к которым можно отнести автоматы, рассмотренныевыше,атакжетакназываемыелинейно-ограниченныеавтоматы,допускающие языки типа 1 (НС-языки).Определение.Линейно-ограниченным автоматом называется шестерка:М = (V1, V2, Q, δ, q0, F),где V1 = {a1, ..., am, Zl, Zp} – конечный входной алфавит;V2 = {А1, ..., Аk} – конечное множество ленточных символов, причемV1 ≤ V2;Q = {q0 , q1, ..., qn-1} – конечное множество состояний;q0 ∈ Q – начальное состояние;F ⊆ Q – множество заключительных состояний;δ – функция, отображающая Q x V2 в множество подмножествQ x V2 x {Л, П}.Множество V1 содержит два специальных символа Zl и Zp, называемыхграничными маркерами, которые не позволяют головке управляющегоустройства уйти с той части ленты, на которой задана входная цепочка.Определение.Формальнолинейно-ограниченныйавтоматявляетсянедетерминированной машиной Тьюринга с ограничением на длину цепочкирассматриваемых символов.
Ситуация линейно-ограниченного автомата иэлементарное действие определяются так же, как и для машины Тьюринга.Определение.136Язык,допускаемыйлинейно-ограниченнымавтоматом,определяется как множество:L(М) = {α | α∈ (V1 – { Zl, Zp })* ∧ (q0, Zl α Zp, 1) ├ * (qf, β, i)},где qf = F, β ∈ V2*, 1 ≤ i ≤ n (n – длина исходной цепочки).В настоящее время неизвестно, является ли класс языков, допускаемыхдетерминированными линейно-ограниченными автоматами, собственнымподклассом класса языков, допускаемых недетерминированными линейноограниченными автоматами.
Однако, для недетерминированных линейноограниченных автоматов установлено, что допускаемые ими языки являютсяНС-языками. Более того, доказано, что для любого НС-языка можнопостроить недетерминированный линейно-ограниченный автомат.4.08. Автоматы с магазинной памятью и бесконтекстные языки.Автоматы и преобразователи с магазинной памятью играют важнуюроль при построении автоматно-лингвистических моделей различногоназначения, связанных с использованием бесконтекстных (контекстносвободных) языков.Вчастности,такиеустройстваиспользуютсявбольшинствеработающих программ для синтаксического анализа программ, написанныхна различных языках программирования, которые во многих случаях можнорассматривать как бесконтекстные.137В отличие от конечных автоматов, рассмотренных ранее, автоматы ипреобразователисмагазиннойпамятьюснабженыдополнительноймагазинной памятью (рабочей лентой) (рис.
4.11).Рис. 4.11. Автоматы с магазинной памятью.Конечное управляющее устройство (УУ) снабжается дополнительнойуправляющей головкой, всегда указывающей на верхнюю ячейку магазиннойпамяти: за один такт работы автомата управляющая головка можетпроизвести следующие движения:1) стереть символ из верхней ячейки (при этом все символы,находящиеся на рабочей ленте, перемещаются на одну ячейку вверх);2) стереть символ из верхней ячейки и записать на рабочую лентунепустую цепочку символов (при этом содержимое рабочей лентысдвигается вниз ровно настолько, какова длина записываемой цепочки).Таким образом, устройство магазинной памяти можно сравнить сустройством магазина боевого автомата; когда в него вкладываетсяпатрон, те, которые уже были внутри, проталкиваются вниз; достать можнотолько патрон, вложенный последним.138Определение.Формально детерминированный магазинный автомат определяетсякак следующая совокупность объектов:М = (V, Q, Vм, δ, q0, z0, F),где V, Q, q0 ∈ Q, F – определяются также, как и для конечногоавтомата;Vм = {z0, z1, ..., zp-1} – алфавит магазинных символов автомата;δ – функция, отображающая множество Q х (V ∪ {ε}) x Vм вмножество Q x Vм, где ε – пустая цепочка;z0 ∈ Vм – так называемый граничный маркер, т.
е. символ, первымпоявляющийся в магазинной памяти.Определение.Недетерминированныймагазинныйавтоматотличаетсяотдетерминированного только тем, что значениями функции переходовявляются не состояния, а множества состояний, то есть функция δотображает множество Q х (V ∪ {ε}) x Vм в множество конечныхподмножеств Q x Vм .Как и в случае конечных автоматов, преобразователи с магазиннойпамятью отличаются от автоматов с магазинной памятью наличиемвыходной ленты.Далее будем рассматривать только недетерминированные магазинныеавтоматы.139Рассмотрим интерпретацию функции δ для такого автомата. Этуфункцию можно представить совокупностью команд вида:(q, a, z) → (q1, γ1), ..., (qm, γm),где q, q1, ..., qm ∈ Q, a ∈ V, z ∈Vм, γ1, ..., γm ∈Vм*.При этом считается, что если на входе читающей головки автоматанаходится символ а, автомат находится в состоянии q, а верхний символрабочей ленты z, то автомат может перейти к состоянию qi , если записать нарабочую ленту цепочку γi (1 ≤ i ≤ m) вместо символа z и передвинутьвходную головку на один символ вправо.Крайний левый символ γi должен при этом оказаться в верхней ячейкемагазина.
Команда (q, ε , z) → (q1, γ1), ..., (qm, γm) означает, что независимо отвходного символа и, не передвигая входной головки, автомат перейдетв состояние qi, заменив символ z магазина на цепочку γi (1 ≤ i ≤ m).Определение.Ситуацией магазинного автомата называется пара (q, γ), где q ∈ Q, γ∈Vм* .Определение.Междуситуациямимагазинногоавтомата(q,γ)и(q′,γ′)устанавливается отношение, обозначаемое символом ├ , если среди команднайдется такая, что (q, ε , z) →(q1, γ1), ..., (qm, γm), причем γ = z β, γ′ = γ i β,q′ = qi для некоторого 1 ≤ i ≤ m (z ∈Vм, β ∈Vм* ).Определение.140Говорят, что магазинный автомат переходит из состояния (q, γ) всостояние (q′, γ′) и обозначают это следующим образом:а : (q, γ) ├ (q′, γ′).Вводится и такое обозначение:а1 ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
