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

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

L₁ (M) = { α | α : (q₀ , z₀ ) ├ _* (q, ε )}

где q Є Q .

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

L ₂ ( M ) = { α | α: ( q ₀ , z ₀ ) ├ _* ( q_f , γ )}

где γ Є V ^* _m , q_f Є F

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

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

M = (V, Q, V_m , δ, q₀ , z₀ , 0),

ГдеV=V_T ; Q={q₀ }; V_M =V_N ; z₀ =S

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

A→a α , a Є V_T , a Є V^* _n

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

(q₀ , a, A)→(q₀ , a)

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

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

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

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

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

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

Р Е Ф Е Р А Т

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

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

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

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

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

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

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