Детерминированные автоматы с магазинной памятью

Определение 12.1.1.

Будем говорить, что два перехода МП-автомата

и

являются совместными, если

1. p1 = p2;

2. или ;

3. или .

Определение 12.1.2.

МП-автомат называется детерминированным (deterministic), если он имеет ровно одно начальное состояние и все переходы этого автомата попарно несовместны.

Пример 12.1.3.

МП-автомат M из примера 10.2.8 не является детерминированным, так как переходы

и

совместны.

Определение 12.1.4.

Язык L над алфавитом

называется детерминированным контекстно-свободным языком, если существует детерминированный МП-автомат, распознающий язык

над алфавитом , где - дополнительный символ, не принадлежащий множеству . Символ

называется маркером конца строки.

Пример 12.1.5.

Рассмотрим алфавит . Язык - детерминированный контекстно-свободный язык, так как язык

порождается детерминированным МП-автоматом (хотя язык L не порождается никаким детерминированным МП-автоматом).

Пример 12.1.6.

Язык L, распознаваемый МП-автоматом M из примера 10.2.8, является детерминированным контекстно-свободным языком, так как язык

порождается детерминированным МП-автоматом

где

Упражнение 12.1.7. Является ли детерминированным контекстно-свободный язык ?

Содержание раздела

---

---