Детерминированные контекстно-свободные языки
Детерминированные контекстно-свободные языки
Детерминированные контекстно‑свободные языки — класс языков, распознаваемых детерминированными автоматами с магазинной памятью.
Общие сведения
Такие языки определяются автоматами, в которых отсутствует неоднозначность переходов.
Для каждого состояния и входного символа существует только один возможный переход.
Этот класс языков обладает строгой детерминацией.
Он замкнут относительно операции дополнения.
Однако не замкнут относительно объединения и пересечения.
Теоретические особенности
Детерминированные контекстно‑свободные языки отличаются от общих контекстно‑свободных языков отсутствием неоднозначности.
Это делает их особенно удобными для алгоритмического анализа.