Автоматы с магазинной памятью — страница 3

  • Просмотров 3962
  • Скачиваний 397
  • Размер файла 10
    Кб

нормаль­ной формой Грейбах, произвольной бесконтекстной грамматики G, то существует недетерминированный магазинный автомат М такой, что L1 (M) = L (G2). При этом M = (V, Q, Vm , δ, q0, z0, 0), Где V=VT; Q={q0}; VM=VN; z0=S а для каждого правила G2 вида A→aα, a Є VT, a Є V*n строится команда отображения δ: (q0, a, A)→(q0, a) Apia логично для любого недетерминированного магазинного автомата М, допускающего язык L1 (M), можно построить бескон­текстную грамматику G

такую, что L (G) = L1 (M). Если для конечных автоматов детерминированные и недетерми­нированные модели эквивалентны по отношению к классу допускае­мых языков, то этого нельзя сказать для магазинных автоматов. Детерминированные автоматы с магазинной памятью допускают лишь некоторое подмножество бесконтекстных языков, которые называют детерминированными бесконтекстными языками. Список использованной литературы КУЗИН Л.Т

«Основы кибернетики» Т.2 УКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ ХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ Р Е Ф Е Р А Т По дискретной математике на тему: «Автоматы с магазинной памятью» Подготовил студент гр. 1киб-30 Кирчатов Роман Романович Преподаватель Бразинская Светлана Викторовна ДНЕПРОПЕТРОВСК, 2002