содержит не более одного элемента

Пусть M = (Q, T, D, q0, F) - НКА. Будем называть M детерминированным конечным автоматом (ДКА), если выполнены следующие два условия:

1. D(q, e) =
   
   , для любого
   
   , и
2. D(q, a) содержит не более одного элемента для любых
   
   и
   
   .

Так как функция переходов ДКА содержит не более одного элемента для любой пары аргументов, для ДКА мы будем пользоваться записью D(q, a)=p вместо D(q, a)={p}.

Конечный автомат может быть изображен графически в виде диаграммы, представляющей собой ориентированный граф, в котором каждому состоянию соответствует вершина, а дуга, помеченная символом соединяет две вершины p и q, если . На диаграмме выделяются начальное и заключительные состояния (в примерах ниже, соответственно, входящей стрелкой и двойным контуром).

Пример 3.3. Пусть L = L(r), где r = (a|b)*a(a|b)(a|b).

1. 1. Недетерминированный конечный автомат M, допускающий язык L:
      
      M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}},
      
      где функция переходов D определяется так:
      
      
      
      Диаграмма автомата приведена на рис. 3.3 а.
   2. Детерминированный конечный автомат M, допускающий язык L:
      
      M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}}
      
      где функция переходов D определяется так:
      
      
      
      
      
      Диаграмма автомата приведена на рис. 3.3 б.
      
      

Рис. 3.3. 

Пример 3.4. Диаграмма автомата, допускающего множество чисел в десятичной записи, приведена на рис. 3.4.


Рис. 3.4. 

Пример 3.5. Анализ цепочек.

1. При анализе цепочки w = ababa автомат из примера рис. 3.3, а, может сделать следующую последовательность тактов:
   
   
   
   Состояние 4 является заключительным, отсюда, цепочка w допускается этим автоматом.
2. При анализе цепочки w = ababab автомат из примера рис. 3.3, б, должен сделать следующую последовательность тактов:
   
   
   
   Так как состояние 7 не является заключительным, цепочка w не допускается этим автоматом.

Содержание  Назад  Вперед

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---

---

---