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

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

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

---

---