Детерминированный автомат с магазинной памятью: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Детерминированный автомат с магазинной памятью''' (''Deterministic pushdown automation'') - ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Детерминированный автомат с магазинной памятью''' (''Deterministic pushdown automation'') | '''Детерминированный автомат с магазинной памятью''' (''[[Deterministic pushdown automation]]'') — | ||
''МП-автомат'' <math>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,</math> <math>F)</math> называется ''детерминированным'' | ''[[МП-Автомат|МП-автомат]]'' <math>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,</math> <math>F)</math> называется ''детерминированным'' (сокращенно ''[[ДМП-Автомат|ДМП-автоматом]]''), если для каждых <math>q\in Q</math> и <math>Z\in\Gamma</math> либо | ||
(сокращенно ''ДМП-автоматом''), если для каждых <math>q\in Q</math> и <math>Z\in\Gamma</math> либо | |||
(1) <math>\delta(q,a,Z)</math> содержит не более одного элемента для | (1) <math>\delta(q,a,Z)</math> содержит не более одного элемента для каждого <math>a\in\Sigma</math> и <math>\delta(q,e,Z)=\emptyset</math>, либо | ||
каждого <math>a\in\Sigma</math> и <math>\delta(q,e,Z)=\emptyset</math>, либо | |||
(2) <math>\delta(q,a,Z)=\emptyset</math> для всех <math>a\in\Sigma</math> и | (2) <math>\delta(q,a,Z)=\emptyset</math> для всех <math>a\in\Sigma</math> и <math>\delta(q,e,Z)</math> содержит не более одного элемента. | ||
<math>\delta(q,e,Z)</math> содержит не более одного элемента. | |||
КС-язык называется ''детерминированным'', если он | [[КС-язык]] называется ''детерминированным'', если он определяется некоторым ДМП-автоматом. Класс | ||
определяется некоторым ДМП-автоматом. Класс | |||
детерминированных КС-языков является собственным подклассом КС-языков. | детерминированных КС-языков является собственным подклассом КС-языков. | ||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
Текущая версия от 13:44, 4 февраля 2011
Детерминированный автомат с магазинной памятью (Deterministic pushdown automation) — МП-автомат [math]\displaystyle{ P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0, }[/math] [math]\displaystyle{ F) }[/math] называется детерминированным (сокращенно ДМП-автоматом), если для каждых [math]\displaystyle{ q\in Q }[/math] и [math]\displaystyle{ Z\in\Gamma }[/math] либо
(1) [math]\displaystyle{ \delta(q,a,Z) }[/math] содержит не более одного элемента для каждого [math]\displaystyle{ a\in\Sigma }[/math] и [math]\displaystyle{ \delta(q,e,Z)=\emptyset }[/math], либо
(2) [math]\displaystyle{ \delta(q,a,Z)=\emptyset }[/math] для всех [math]\displaystyle{ a\in\Sigma }[/math] и [math]\displaystyle{ \delta(q,e,Z) }[/math] содержит не более одного элемента.
КС-язык называется детерминированным, если он определяется некоторым ДМП-автоматом. Класс детерминированных КС-языков является собственным подклассом КС-языков.
Литература
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
- Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
- Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.