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

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

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

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

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

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

    В отличие от конечных автоматов и преобразователей,

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

    На рис. 1

    такой преобразователь.

    Конечное

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

    верхнюю ячейку магазинной памяти; за один такт работы автомата

    (преобразователя)

    управляющая головка может произвести следующие движения:

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

    одну

    ячейку

    вверх);

    2) стереть

    символ

    из

    верхней ячейки

    и записать

    на рабочую ленту

    непустую цепочку символов (при этом содержимое

    рабочей

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

    какова длина

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

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

    вниз; до­стать можно только патрон, вложенный последним.

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

    M = (V, Q, V

    ...

    Забрать файл

    Похожие материалы:


    Добавить комментарий
    Старайтесь излагать свои мысли грамотно и лаконично

    Введите код:
    Включите эту картинку для отображения кода безопасности
    обновить, если не виден код



ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены