Нормальная форма ДМП-автомата — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(init)
(нет различий)

Версия 01:32, 31 декабря 2016

Определение:
ДМП в атомарной нормальной форме (англ. Atomic Normal Form) называется такой детерминированный автомат с магазинной памятью [math]M[/math], которой удовлетворяет следующим условиям:
  1. Множество состояний [math]M[/math] состоит из трёх непересекающихся подможеств: [math]K_{read}[/math], [math]K_{push}[/math] и [math]K_{pop}[/math] (состояния, из которых нет переходов, находятся в [math]K_{read}[/math]).
  2. Переходы представлены в виде одной из следующих форм:
    1. read переход — находясь в read состоянии, автомат считывает следующий символ входной строки, не смотря на верхушку стека, и переходит в новое состояние, не меняя стек. Это единственный переход обрабатывающий входные данные.
    2. push переход — находясь в push состоянии, автомат делает [math]\varepsilon[/math]-переход, кладёт текущее состояние на верхушку стека и менеят состояние (не смотря на верхушку стека).
    3. pop переход — находясь в pop состоянии, автомат делает [math]\varepsilon[/math]-переход, снимает символ с верхушки стека и переходит в новое состояние.
  3. pop переход никогда не идёт после push перехода.
  4. Все допускающие состояния — read состояния.