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

Материал из Википедии — свободной энциклопедии

Эту статью или раздел следует викифицировать.
Пожалуйста, оформите её согласно общим правилам и указаниям.

Автомат с магазинной памятью является расширением абстракции конечных автоматов.

В отличии от конечных автоматов, автомат с магазинной памятью является набором:

$\boldsymbol{M = (K , \Sigma , \pi , s , F, S, \epsilon)}$

Где K — конечное множество состояний автомата, $s \in K$ — единственно допустимое начальное состояние автомата, $F \subset K$ — множество конечных состояний, причём допустимо F=Ø, и F=K, Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом, S — алфавит памяти (магазина), $\epsilon \in S$ — нулевой символ памяти. Память работает как стек, то есть для чтения доступен последний записанный в неё элемент. Таким образом, функция перехода является отображением $\pi : K \times \Sigma \times S \rightarrow K \times S$ . То есть, по комбинации текущего состояния, входного символа и символа на вершине магазина автомат выбирает следующее состояние и, возможно, символ для записи в магазин. В случае, когда в правой части автоматного правила присутствует $ε$ , в магазин ничего не добавляется, а элемент с вершины стирается. Если магазин пуст, то срабатывают правила с $ε$ в левой части.

В чистом виде автоматы с магазинной памятью используются крайне редко. Обычно это модель используется для наглядного представления отличия обычных конечных автоматов от синтаксических грамматик. Реализация автоматов с магазинной памятью отличается от конечных автоматов тем, что текущее состояние автомата сильно зависит от любого предыдущего.

Это незавершённая статья по математике.
Вы можете помочь проекту, исправив и дополнив её.

Категории: Википедия:Статьи к викификации | Незавершённые статьи по математике | Теория алгоритмов

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

Материал из Википедии — свободной энциклопедии

Views

Навигация

Участие

Поиск

На других языках