Дискретная математика: графы и автоматы. Альпин Ю.А - 61 стр.

§ 1. Буквы, слова, языки, автоматы.                                  61


    Интерес представляют не любые множества слов, а те, которые
возникают при решении задач математики, лингвистики, програм-
мирования — задач, связанных с переработкой информации. Такими
множествами слов являются, в частности, языки, распознаваемые ко-
нечными автоматами.
    Автомат — это совокупность (X, S, δ), где X — алфавит, S —
непустое множество, элементы которого называются состояниями
автомата, δ — функция из S × X в S, она называется функцией пе-
рехода.
    Запись δ(s, x) = s0 читается так: автомат под действием сигнала
(буквы) x ∈ X переходит из состояния s в состояние s0 .
    Автомат называется конечным, если множество его состояний ко-
нечное. Конечный автомат можно задать таблицей. Например, таб-
лица
      a b       задает автомат с алфавитом X = {a, b} и множе-
  1 2 3         ством состояний S = {1, 2, 3, 4, 5, 6, 7}, переходы ко-
  2 4 5         торого определены очевидным образом: например,
  3 3 3         δ(2, b) = 5, δ(5, a) = 3 и так далее. Автомат удоб-
  4 3 6         но изображать в виде орграфа. При этом верши-
  5 3 3         ны обозначают состояния, и дуга ведёт из s в s0 ⇔
  6 3 7         δ(s, x) = s0 для некоторой буквы x. Все такие буквы
  7 3 3         считаются метками этой дуги.
    Автомат, заданный выше таблицей, изображается графом




                                      Рис. 1

   Заметим, что любой граф с множеством вершин S, дуги которого
помечены буквами алфавита X так, что для любой пары (s, x) ∈
S × X имеется ровно одна дуга с началом s, помеченная буквой x,
определяет автомат. Действительно, будем считать, что конец этой
дуги указывает на состояние, в которое автомат переходит из s под
действием x. Этим функция перехода полностью определяется.
   Вот еще один пример графа автомата и соответствующей ему таб-
лицы: