Детерминированный автомат с магазинной памятью: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Детерминированный автомат с магазинной памятью''' (''[[Deterministic pushdown automation]]'') -  
'''Детерминированный автомат с магазинной памятью''' (''[[Deterministic pushdown automation]]'') -  
''[[МП-автомат]]'' <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>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,</math> <math>F)</math> называется ''детерминированным'' (сокращенно ''[[ДМП-Автомат|ДМП-автоматом]]''), если для каждых <math>q\in Q</math> и <math>Z\in\Gamma</math> либо  


(1) <math>\delta(q,a,Z)</math> содержит не более одного элемента для каждого <math>a\in\Sigma</math> и <math>\delta(q,e,Z)=\emptyset</math>, либо
(1) <math>\delta(q,a,Z)</math> содержит не более одного элемента для каждого <math>a\in\Sigma</math> и <math>\delta(q,e,Z)=\emptyset</math>, либо

Версия от 18:28, 14 октября 2009

Детерминированный автомат с магазинной памятью (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] содержит не более одного элемента.

КС-язык называется детерминированным, если он определяется некоторым ДМП-автоматом. Класс детерминированных КС-языков является собственным подклассом КС-языков.

Литература

[Ахо-Ульман],

[Касьянов/95],

[Касьянов-Поттосин]