48
правок
Изменения
init
{{Определение
|definition=ДМП в '''атомарной нормальной форме''' (англ. ''Atomic Normal Form'') называется такой [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку|детерминированный автомат с магазинной памятью]] <tex>M</tex>, которой удовлетворяет следующим условиям:
# Множество состояний <tex>M</tex> состоит из трёх непересекающихся подможеств: <tex>K_{read}</tex>, <tex>K_{push}</tex> и <tex>K_{pop}</tex> (состояния, из которых нет переходов, находятся в <tex>K_{read}</tex>).
# Переходы представлены в виде одной из следующих форм:
## '''read''' переход {{---}} находясь в '''read''' состоянии, автомат считывает следующий символ входной строки, не смотря на верхушку стека, и переходит в новое состояние, не меняя стек. Это единственный переход обрабатывающий входные данные.
## '''push''' переход {{---}} находясь в '''push''' состоянии, автомат делает <tex>\varepsilon</tex>-переход, кладёт текущее состояние на верхушку стека и менеят состояние (не смотря на верхушку стека).
## '''pop''' переход {{---}} находясь в '''pop''' состоянии, автомат делает <tex>\varepsilon</tex>-переход, снимает символ с верхушки стека и переходит в новое состояние.
# '''pop''' переход никогда не идёт после '''push''' перехода.
# Все допускающие состояния {{---}} '''read''' состояния.
}}
|definition=ДМП в '''атомарной нормальной форме''' (англ. ''Atomic Normal Form'') называется такой [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку|детерминированный автомат с магазинной памятью]] <tex>M</tex>, которой удовлетворяет следующим условиям:
# Множество состояний <tex>M</tex> состоит из трёх непересекающихся подможеств: <tex>K_{read}</tex>, <tex>K_{push}</tex> и <tex>K_{pop}</tex> (состояния, из которых нет переходов, находятся в <tex>K_{read}</tex>).
# Переходы представлены в виде одной из следующих форм:
## '''read''' переход {{---}} находясь в '''read''' состоянии, автомат считывает следующий символ входной строки, не смотря на верхушку стека, и переходит в новое состояние, не меняя стек. Это единственный переход обрабатывающий входные данные.
## '''push''' переход {{---}} находясь в '''push''' состоянии, автомат делает <tex>\varepsilon</tex>-переход, кладёт текущее состояние на верхушку стека и менеят состояние (не смотря на верхушку стека).
## '''pop''' переход {{---}} находясь в '''pop''' состоянии, автомат делает <tex>\varepsilon</tex>-переход, снимает символ с верхушки стека и переходит в новое состояние.
# '''pop''' переход никогда не идёт после '''push''' перехода.
# Все допускающие состояния {{---}} '''read''' состояния.
}}
