Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Магазинный автомат

Читайте также:
  1. Автоматизация процесса назначения IP-адресов узлам сети - протокол DHCP
  2. АВТОМАТИЗАЦИЯ РАБОТЫ МАРТЕНОВСКОЙ ПЕЧИ
  3. Автоматизированная система централизованной подготовки и оформления перевозочных документов
  4. Автоматизированное производство.
  5. АВТОМАТИЗИРОВАННОЕ РАБОЧЕЕ МЕСТО МЕНЕДЖЕРА ПО ПРОДАЖЕ АВТОМОБИЛЕЙ
  6. Автоматизированные линии обработки яиц
  7. Автоматизированные транспортно-накопительные системы ГАП

В общем виде МП-автомат можно определить следующим образом:

R(Q, V, Z, d,q0,z0,F),

где Q — множество состояний автомата;

V — алфавит входных символов автомата;

Z — специальный конечный алфавит магазинных символов автомата (обычно он включает в себя алфавиты терминальных и нетерминальных символов грамматики),

V Í Z;

d — функция переходов автомата, которая отображает множество Qx(V È{l})xZ на конечное множество подмножеств P(QxZ');

q 0 Î Q — начальное состояние автомата;

z0 Î Z — начальный символ магазина;

F Í Q — множество конечных состояний.

МП-автомат в отличие от обычного конечного автомата (КА) имеет стек (магазин), в который можно помещать специальные «магазинные» символы (обычно это терминальные и нетерминальные символы грамматики языка). Переход из одного состояния в другое зависит не только от входного символа, но и от одного или нескольких верхних символов стека. Таким образом, конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положением указателя в цепочке) и содержимым стека.

 

 

Рисунок 2 -3. Общая условная схема автомата с магазинной памятью (МП-автомата)

 

При выполнении такта (перехода) из стека удаляется верхний символ, соответствующий условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при которых входной символ игнорируется (и тем самым он будет входным символом и следующем переходе). Эти переходы (такты) называются l-переходами (l-тактами). Аналогично, автомат не обязательно должен извлекать символ из стека — гда z=l., этого не происходит.

МП-автомат допускает (принимает) цепочку символов, если, получив эту цепочку на вход, он может перейти в одну из конечных конфигураций, — когда при окончании цепочки автомат находится в одном из конечных состояний, а стек содержит некоторую определенную цепочку. Тогда входная цепочка принимается (после окончания цепочки автомат может сделать произвольное количество l - переходов). Иначе цепочка символов не принимается.

 


Дата добавления: 2015-07-07; просмотров: 105 | Нарушение авторских прав


Читайте в этой же книге: Восстанавливаемость | Этапы подготовки программы к выполнению | Операнды команд | Заголовок макроопределения | Присваивание значений переменным макроопределения | Оператор безусловного перехода и метки макроопределения | Тема 2.2.Трансляторы | Лексический, синтаксический и семантический анализаторы | Генератор кода. Распределение памяти. Виды переменных | Тема 2.3 Формальные языки и грамматики |
<== предыдущая страница | следующая страница ==>
Вывод цепочек| Пример 1

mybiblioteka.su - 2015-2021 год. (0.013 сек.)