Предыдущая страница реферата | 1  2

Вводится и такое обозначение: a1...an: (q, ?)+ * (q’, ?’), если справедливо, что

ai: (qi, ?i)+ (qi+1, ?i+1), 1 ? i ? m

где ai Є V, ?1 = ?, ?2,…, ?n+1 = ?’ Є V*m q1 = q, q2,…, qn+1 = q’ Є Q
Существует два способа определения языка, допускаемого магазинным автоматом. Согласно первому способу считается, что входная цепочка
? Є V* принадлежит языку L1 (M) тогда, когда после просмотра последнего символа, входящего в эту цепочку, в магазине автомата М будет находиться пустая цепочка ?. Другими словами,

L1 (M) = ?

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

L2 (M) = ?

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

M = (V, Q, Vm , ?, q0, z0, 0),
Где V=VT; Q={q0}; VM=VN; z0=S а для каждого правила G2 вида

a?, a Є VT, a Є V*n

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

(q0, a, A)>(q0, a)

Apia логично для любого недетерминированного магазинного автомата М, допускающего язык L1 (M), можно построить бесконтекстную грамматику G такую, что L (G) = L1 (M).
Если для конечных автоматов детерминированные и недетерминированные модели эквивалентны по отношению к классу допускаемых языков, то этого нельзя сказать для магазинных автоматов. Детерминированные автоматы с магазинной памятью допускают лишь некоторое подмножество бесконтекстных языков, которые называют детерминированными бесконтекстными языками.

Список использованной литературы

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

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

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

Р Е Ф Е Р А Т

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

«Автоматы с магазинной памятью»

Подготовил студент гр. 1киб-30

Кирчатов Роман Романович

Преподаватель

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

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

Скачали данный реферат: Флавиан, Висенин, Reshetnikov, Феодосия, Kosma, Купревич.
Последние просмотренные рефераты на тему: титульный лист реферата, банки рефератов, взаимодействие реферат, сочинение тарас.





Предыдущая страница реферата | 1  2