Реферат

Реферат Автоматы с магазинной памятью

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 8.11.2024




АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ



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

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

На рис. 1



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

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

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

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

рабочей  ленты сдвигается вниз ровно настолько,  какова длина

с   записываемой цепочки).

Таким образом, устройство магазинной памяти можно сравнить с устройством магазина боевого автомата: когда в него вкладывается патрон, те, которые уже были внутри, проталкиваются вниз; до­стать можно только патрон, вложенный последним.

Формально детерминированный магазинный автомат определя­ется как следующая совокупность объектов:

M = (V, Q, VM,
δ, q0, z0, F),

 где V, Q, q0 Є Q, F определяются так же, как и для конечного автомата;

VM = {z0, z1,…,zp-1} — алфавит магазинных символов авто­мата;

δ — функция, отображающая множество Q

X
(
V
U { ε }) X

VM

в множество Q

X

VM
, где е — пустая цепочка;
 
z0 Є VM — так называемый граничный маркер,  т. е.  символ,
первым появляющийся в магазинной памяти.


Недетерминированный магазинный автомат отличается от де­терминированного только тем, что функция δ отображает множество Q

X
(
V
U { ε }) X

VM
. в множество конечных подмножеств Q

x

VM

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

Далее будем рассматривать только недетерминированные магазин­ные автоматы.

Рассмотрим  интерпретацию функции δ для  такого  автомата. Эту функцию можно представить совокупностью команд вида

(q, a, z)→(q1, γ1),…,(qm, γm),

где q, q1,…qm Є Q, a Є V, z Є VM, γ1,…,γm Є V*m
При этом считается, что если на входе читающей головки авто­
мата находится символ а, автомат находится в состоянии
q, а верхний символ рабочей ленты z, то автомат может перейти к состоянию qi, записав при этом на рабочую ленту цепочку  γi(1 i m)
вместо символа
z, передвинуть входную головку на один символ
вправо так, как это показано на рис. 1, и перейти в состояние qi. Крайний левый символ
γi должен при этом оказаться в верхней
ячейке магазина. Команда (
q
,
e
,
z
)→(
q
1
,
γ
1
),…, (
qm, γm) означает,
что независимо от входного символа и, не передвигая входной го- +
ловки, автомат перейдет в состояние qi, заменив символ
z магазина
на цепочку
γi(1 i
m
).
                                  

Ситуацией магазинного автомата называется пара (q
,
γ
)
, где

q
Є
Q
, γ
Є
V
*
m
. Между ситуациями магазинного автомата (q
,
γ
)
и

(
q
’,
γ
’)
,  устанавливается отношение, обозначаемое символом ├, если среди команд найдется такая, что

(q, a, z)→(q1, γ1),…,(qm, γm),

причем γ = zβ, γ’ = γiβ q' = qi для некоторого 1 ≤ i ≤ m (z Є
Vm,


β
Є
V*m  ).



Говорят, что магазинный автомат переходит из состояния (q
,
γ
)
в состояние (q
’,
γ
’)
и обозначают это следующим образом:

a: (q, γ)├ (q’, γ’).

 Вводится и такое обозначение:

a1...an: (q, γ)├
*
(q’, γ’),


если справедливо, что

ai: (qi, γi)├ (qi+1, γi+1), 1 ≤ i ≤ m

где

ai
Є
V
,
γ
1
=
γ
,
γ
2
,…,
γn
+1
=
γ
’ Є
V
*
m
 


q
1
=
q
,
q
2
,…,
qn
+1
=
q
’ Є
Q
 


Существует два способа определения языка, допускаемого ма­газинным  автоматом.   Согласно   первому  способу  считается,   что входная цепочка α Є V
*
принадлежит языку L
1
(
M
)
тогда, когда после просмотра последнего символа,  входящего в эту цепочку,

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

L1 (M) = {
α
|
α
: (q0, z0) ├
*
(q,
ε
)}


где q Є Q.

Согласно второму способу считается, что входная цепочка при­надлежит языку L
2
(
M
)
тогда, когда после просмотра последнего символа, входящего в эту цепочку, автомат М окажется в одном из своих заключительных состояний q
f
Є
F
. Другими словами,

L
2
(
M
) = { α | α: (
q
0
,
z
0
) ├
*
(
qf
,
γ
)}


где γ
Є
V
*
m
,
qf

Є
F
 


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

Доказано также, что если L
(
G
2
)
— бесконтекстный язык, по­рождаемый Грамматикой G2 = (Vx
,
VT
,
Р,
S
)
, являющейся нормаль­ной формой Грейбах, произвольной бесконтекстной грамматики G, то существует недетерминированный магазинный автомат М такой, что L
1
(
M
) =
L
(
G
2
).
При этом

M = (V, Q, Vm , δ, q0, z0, 0),

Где V=VT; Q={q0}; VM=VN; z0=S

а для каждого правила G
2
вида

A→a
α
, a
Є
VT, a
Є
V*n


строится команда отображения δ:

(q0, a, A)→(q0, a)

Apia логично для любого недетерминированного магазинного автомата М, допускающего язык L
1
(
M
)
, можно построить бескон­текстную грамматику G такую, что L
(
G
) =
L
1
(
M
).


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

КУЗИН Л.Т «Основы кибернетики» Т.2

УКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ

ХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

Р Е Ф Е Р А Т

По дискретной математике на тему:

«Автоматы с магазинной памятью»
Подготовил студент гр. 1киб-30

Кирчатов Роман Романович
Преподаватель

Бразинская Светлана Викторовна

ДНЕПРОПЕТРОВСК, 2002

1. Реферат Плазма и ее применение
2. Реферат Особенности деловых переговоров и их характер
3. Доклад Джон Мейнард Кейнс 2
4. Реферат Анализ сущности инфляции
5. Контрольная работа на тему Гражданские права
6. Реферат на тему World War 2 2 Essay Research Paper
7. Реферат на тему Shadow Of A Doubt To Catch A
8. Реферат на тему Конюнктура товарно-сировинних бірж
9. Реферат Суб єкти сучасної української політики в інтернет
10. Реферат Анализ и формирование организационных структур управления