38
правок
Изменения
Новая страница: «{{Определение |definition = Определим <tex>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)</tex> как <b>детерминированный автомат…»
{{Определение
|definition =
Определим <tex>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)</tex> как <b>детерминированный автомат с магазинной (стековой) памятью</b>, где <br>
* <tex>Q</tex>: конечное множество состояний.
* <tex>\Sigma</tex>: конечное множество входных символов.
* <tex>\Gamma</tex>: конечный магазинный алфавит {{---}} множество символов, которые можно помещать в магазин.
* <tex>\delta</tex>: функция переходов. <tex>\delta (q,a,X)=(p,\gamma)</tex>, где
** <tex>q</tex>: текущее состояние из Q.
** <tex>a</tex>: либо входной символ, либо пустая цепочка <tex>\epsilon</tex>.
** <tex>X</tex>: магазинный символ из <tex>\Gamma</tex>.
** <tex>p</tex>: новое состояние из Q.
** <tex>\gamma</tex>: цепочка магазинных символов, <i>замещающих</i> <tex>X</tex> на вершине магазина.
* <tex>q_0</tex>: начальное состояние.
* <tex>Z_0</tex>: начальный магазинный символ (маркер дна). Находится в магазине в начале работы автомата.
* <tex>F</tex>: множество допускающих состояний.
}}
|definition =
Определим <tex>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)</tex> как <b>детерминированный автомат с магазинной (стековой) памятью</b>, где <br>
* <tex>Q</tex>: конечное множество состояний.
* <tex>\Sigma</tex>: конечное множество входных символов.
* <tex>\Gamma</tex>: конечный магазинный алфавит {{---}} множество символов, которые можно помещать в магазин.
* <tex>\delta</tex>: функция переходов. <tex>\delta (q,a,X)=(p,\gamma)</tex>, где
** <tex>q</tex>: текущее состояние из Q.
** <tex>a</tex>: либо входной символ, либо пустая цепочка <tex>\epsilon</tex>.
** <tex>X</tex>: магазинный символ из <tex>\Gamma</tex>.
** <tex>p</tex>: новое состояние из Q.
** <tex>\gamma</tex>: цепочка магазинных символов, <i>замещающих</i> <tex>X</tex> на вершине магазина.
* <tex>q_0</tex>: начальное состояние.
* <tex>Z_0</tex>: начальный магазинный символ (маркер дна). Находится в магазине в начале работы автомата.
* <tex>F</tex>: множество допускающих состояний.
}}
