Материал: Лабораторная работа #3

Лабораторная работа №3 Недетерминированные магазинные автоматы. Теоретическая часть

Модель магазинного автомата (рис.1) состоит из

• входной ленты,

• устройства управления и

• в спомогательной ленты, называемой магазином или стеком.

Рис.1. Модель магазинного автомата

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

Вспомогательная лента также разделена на клетки, в которых могут располагаться символы магазинного алфавита. Начало вспомогательной ленты называется дном магазина. Связь устройства управления с лентами осуществляется двумя головками, которые могут перемещаться вдоль лент.

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

• при записи головка предварительно сдвигается на одну позицию вверх, а затем символ заносится на ленту,

• при чтении символ, находящийся под головкой считывается с ленты, а затем головка сдвигается на одну позицию вниз, т.о. головка всегда установлена против последнего записанного символа. Позицию, находящуюся в рассматриваемый момент времени под головкой, называют вершиной магазина.

Определение. Магазинный автомат М определяется следующей совокупностью семи объектов: M={S, P, Z, , s_о, h_о, F}, где

S - алфавит состояний,

P - входной алфавит,

Z - алфавит магазинных символов, записываемых на вспомогательную ленту,

 - функция переходов,  : {S x P  {} x H}  S x H*, если М-автомат - детерминированный, и  : {S x P  {} x H}  2^S x H*, если М-автомат - недетерминированный.

s_о - начальное состояние, s_о  S.

h_о- маркер дна, он всегда записывается на дно магазина , h_о  H.

F - множество конечных состояний. F является подмножеством S.

Функция  отображает тройки (p_i , s_j , h_k) в пары (s_r , ) , где   H* и h_k - символ в вершине магазина, для детерминированного автомата или в множество таких пар для недетерминированного автомата.

Эта функция описывает изменение состояния магазинного автомата, происходящее при чтении символа с входной ленты и перемещении входной головки.

В дальнейшем при построении магазинных автоматов потребуются две разновидности функций переходов:

1. функция переходов с пустым символом в качестве входного символа:

⁰(s, , h) = (s', ), которая, независимо от того, какой символ находится под читающей головкой входной ленты, предписывает прочитать символ h из вершины магазина, изменить состояние автомата на s' и записать цепочку  в магазин.

2) функция переходов с определенным входным символом:

 (s, a, h) = (s', ), которая предписывает прочитать входной символ а, изменить состояние автомата на s’ и заменить верхний символ магазина h цепочкой .

Работа магазинного автомата

Чтобы описать, как работает автомат, введем понятие конфигурации.

Определение. Конфигурацией автомата М называют тройку (s, , )S x P* x H*, где

s - текущее состояние управляющего устройства,

 - неиспользованная часть входной цепочки P*, самый левый символ этой цепочки находится под головкой. Если a =  , то считается, что вся входная цепочка прочитана.

 - цепочка, записанная в магазине, H*, самый правый символ цепочки считается вершиной магазина. Если =, то магазин пуст.

Работа автомата может быть представлена как смена конфигураций. Один такт работы автомата заключается в определении новой конфигурации по заданной. Это записывается так:

(s, a, h ) ├ (s', , )

Такая смена конфигураций возможна, если функция (s, a, h ) (или (s, , h)) определена и имеет значение (s', ). При этом предполагается, что автомат

• читает символ a, находящийся под головкой. Или не читает ничего, в случае входного символа .

• определяет новое состояние s'

• читает символ h, находящийся в вершине магазина и

• записывает цепочку  в магазин вместо символа h. Если  = , то верхний символ оказывается удаленным из магазина.

Таким образом, могут быть три случая при работе автомата:

• (s, a, h) определена и выполняется такт работы,

• (s, a, h) не определена, но определена функция (s, , h) и выполняется пустой такт (без чтения входной информации).

• функции (s, a, h) и (s, , h) не определены, в этом случае дальнейшая работа автомата невозможна.

Начальной конфигурацией называется конфигурация (s₀, , h₀), где s₀ - начальное состояние,  - исходная цепочка, h₀ - маркер дна магазина.

Заключительная конфигурация – (s, , ), где s принадлежит множеству заключительных состояний F.

Для обозначения последовательности сменяющих друг друга конфигураций условимся использовать знак ├*. Таким образом последовательность

( s₁, ₁, ₁ ) ├ ( s₂, ₂, ₂) ├ ... ├ ( s_n, _n,_n )

записывается в сокращенном виде как:

(s₁, ₁, ₁ ) ├* ( s_n, _n, _n ).

Язык, допускаемый магазинным автоматом

Определение. Цепочка  называется допустимой для автомата М, если существует последовательность конфигураций, в которой первая конфигурация является начальной c цепочкой , а последняя – заключительной. (s_о, , h_о) ├* (s₁,  , ) , где s₁  F .

Определение. Множество цепочек, допускаемых автоматом М, называется языком, допускаемым или определяемым автоматом М, и обозначается L(М).

L(М)= { | ( s_о, , h_о ) ├* ( s', , ) и s'  F }

Чтобы лучше представить себе работу магазинного автомата, рассмотрим два примера. Пусть задан магазинный автомат М₁ в следующем виде:

М₁: P = {a , b}; S = {s₀ , s₁ , s₂}; Z = {h₀ , a}; F = {s₀};

 (s₀ , a , h₀) = (s1 , h₀a),

 (s₁ , a , a) = (s₁ , aa),

 (s₁ , b , a) = (s₂ , ),

 (s₂ , b , a) = (s₂ , ),

 (s₂ ,  , h₀) = (s₀ , ).

Этот автомат является детерминированным, поскольку каждому набору аргументов соответствует единственное значение функции. Работу автомата при распознавании входной цепочки aabb можно представить в виде последовательности конфигураций:

(s₀,aabb,h₀) ├ (s₁,abb,h₀a) ├ (s₁,bb,h₀aa) ├ (s₂,b,h₀a) ├ (s₂,,h₀) ├ (s₀,,) .

Нетрудно проверить, что при задании входной цепочки aabbb автомат не сможет закончить работу. Следовательно, эта цепочка не принадлежит языку, допускаемому автоматом M₁.

Магазинный автомат М₂, заданный следующим описанием:

М₂: P = {a , b}; S = {s₀, s₁ , s₂}; Z = {h₀, a , b}; F = {s₂};

(1)  (s₀ , a , h₀) = (s₀, h₀a),

(2)  (s₀ , b , h₀) = (s₀, h₀b),

(3)  (s₀ , a , a) = {(s₀,aa) , (s₁ , )},

(4)  (s₀ , b , a) = (s₀,ab),

(5)  (s₀ , a , b) = (s0 , ba),

(6)  (s₀ , b , b) = {(s₀ , bb) , (s₁ , )},

(7)  (s₁ , a , a) = (s₁, ),

(8)  (s₁ , b , b) = (s₁, ),

(9)  (s₂ ,  , h₀) = (s₂ , ),

является недетерминированным автоматом, поскольку одному и тому же набору аргументов, например (s_о , a, a), соответствуют два значения функции. Работу автомата рассмотрим для входной цепочки abba. Если использовать последовательность команд (1),(4),(6.1),(5), то получим последовательность конфигураций:

(s₀,abba,h₀)

├ (s₀,bba,h₀a), (1)

├ (s₀,ba,h₀ab), (4)

├ (s₀,a,h₀abb), (6.1)

├ (s₀,,h₀abba). (5)

которая показывает, что дальнейшая работа невозможна, т.к. входная цепочка прочитана и переход (s₀,,h₀abba) не определен. Если же использовать последовательность команд (1),(4),(6.2),(3),(9), то получим заключительную конфигурацию:

(s₀,abba,h₀)

├ (s₀,bba,h₀a), (1)

├ (s₀,ba,h₀ab), (4)

├ (s1,a,h₀a), (6.2)

├ (s₁,,h₀), (3)

├ (s2,,) . (9).

Т.о. можно сделать вывод о том, что цепочка abba допускается автоматом М₂.

Построение магазинного автомата

Пусть задана грамматика G = {VN, VT, I, P}. Определим компоненты автомата М следующим образом:

S = {s₀}, P = VT, Z = VN  VT  {h₀} , F = {s₀},

в качестве начального состояния автомата примем s₀ и построим функцию переходов так:

1. Для всех A  VN таких, что встречаются в левой части правил A  , построим команды вида:

⁰(s₀, , A) = (s₀, ^R ),

где ^R – реверс цепочки  .

2. Для всех a VT построим команды вида

 ( s₀, a, a) = ( s₀, )

3. Для перехода в конечное состояние построим команду

 ( s₀, , h₀) = ( s₀, )

4. Начальную конфигурацию автомата определим в виде:

( s₀, , h₀ I),

где  – исходная цепочка, записанная на входной ленте.

Автомат, построенный по приведенным выше правилам, работает следующим образом. Если в вершине магазина находится терминал, и символ, читаемый с входной ленты, совпадает с ним, то по команде типа (2) терминал удаляется из магазина, а входная головка сдвигается. Если же в вершине магазина находится нетерминал, то выполняется команда типа (1), которая вместо терминала записывает в магазин цепочку, представляющую собой правую часть правила грамматики. Следовательно, автомат, последовательно заменяя нетерминалы, появляющиеся в вершине магазина, строит в магазине левый вывод входной цепочки, удаляя полученные терминальные символы, совпадающие с символами входной цепочки. Это означает, что каждая цепочка, которая может быть получена с помощью левого вывода в грамматике G, допускается построенным автоматом М.

Пример построения автомата

Процедуру построения автомата рассмотрим на примере грамматики с правилами:

E  E + T | T

T  T * F | F

F  ( E ) | a

Для искомого автомата имеем:

P = {a, +, *, ), ( }, Z = {E, T, F, a, +, *) , h₀, ( }, S = {s₀ }, F = {s₀}

Для всех правил грамматики строим команды типа (1):

1. ⁰ (s₀ ,  , E) = {(s₀ , T+E) ; (s₀ , T)},

2. ⁰ (s₀ ,  , T) = {(s₀ , F*T) ; (s₀ , F)},

3. ⁰ (s₀ ,  , F) = {(s₀ , (E) ) ; (s₀ , a)},

Для всех терминальных символов строим команды типа (2):

4.  ( s₀, a, a ) = ( s₀,  ),

5.  ( s₀ , + , + ) = (s₀ ,  ),

6.  ( s₀ , * , * ) = (s₀ ,  ),

7.  ( s₀ , ( , ( ) = (s₀ ,  ),

8.  ( s₀ , ) , ) ) = (s₀ ,  ),

Для перехода в конечное состояние построим команду:

(9)  (s₀ ,  , h₀) = ( s₀ ,  ).