Математическая теория формальных языков

         

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


Определение 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. Является ли детерминированным контекстно-свободный язык ?



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