Еще один способ задания автоматов – ориентированный мультиграф, называемый графом переходов или диаграммой переходов. Вершины графа переходов соответствуют состояниям. Если δ (qi,xj) = qk и λ (qi,xj) = yl , то из вершины qi в вершину qj ведет ребро, на котором написаны пара xj, yl . Для любого графа переходов выполняются следующие условия корректности:

a) для любой входной буквы xj имеется ребро, выходящее из qi , на котором написано xj (условие полноты);

b) любая буква xj встречается только на одном ребре, выходящем из вершины qi (условие непротиворечивости или детерминированности).

На графе переходов наглядно представимы все функции, определяе мые формулами (4.1.1) - (4.1.4). Если зафиксирована вершина qi , то всякое слово x = k i i i x x ...x 1 2 однозначно определяет путь длины k из этой вершины (обозначим его qix), на k ребрах которого написаны k i i i x x ...x 1 2 . Поэтому δ(qix) − это последняя вершина пути qix; λ (qix) − выходная буква, написан ная на последнем ребре пути qix , а отображение S(qix)− слово, образованное выходными буквами на k ребрах пути qix.

---

Смотрите также файлы

• Инструкция по охране труда логиста (Подготовлен для системы, 2021).docx

• СабаТЫ таырыбы. Лас ас тзын тазарту Масаты.docx

• Темы презентаций по дисциплине Аудит Понятия, цели и задачи аудиторской деятельности.docx

• Инструктаж на весенние каникулы.pdf

• Совершенствование взаимоотношений местных органов власти с предприятиями и организациями жилищнокоммунального комплекса.docx