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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Детерминированный автомат с магазинной памятью''' (''Deterministic pushdown automation'') - ...)
 
Нет описания правки
Строка 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> содержит не более одного элемента.


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

Навигация