Детерминированные конечные автоматы

Определение 2.6.1. Конечный автомат называется детерминированным (deterministic), если

  1. множество I содержит ровно один элемент;
  2. для каждого перехода выполняется равенство |x| = 1 ;
  3. для любого символа и для любого состояния существует не более одного состояния со свойством .

Пример 2.6.2. Конечный автомат из примера 2.1.14 является детерминированным.

Определение 2.6.3. Детерминированный конечный автомат называется полным (complete), если для каждого состояния и для каждого символа найдется такое состояние , что .

Пример 2.6.4. Конечный автомат из примера 2.1.14 эквивалентен полному детерминированному конечному автомату , где Q = {1,2,3}, , I = {1}, F = {1,2},

Замечание 2.6.5. Некоторые авторы используют в определении полного детерминированного конечного автомата вместо отношения функцию . От функции можно перейти к отношению , положив

Упражнение 2.6.6. Является ли детерминированным следующий конечный автомат?

Упражнение 2.6.7. Является ли полным следующий детерминированный конечный автомат с алфавитом ?