Читайте также:
|
1. Автоматная таблица.
Таблицы переходов d(qiaj) = ql и выходов l(qiaj) = bk, имеет вид
| A Q | a1 | ... | aj | ... | am | B Q | a1 | ... | aj | ... | am | |
| q0 | q2 | … | ql | … | qp | q0 | B8 | … | bi | … | bt | |
| … | … | … | … | … | … | … | … | … | … | … | … | |
| qi | q4 | … | qr | … | qm | qi | B7 | … | bl | … | br | |
| … | … | … | … | … | … | … | … | … | … | … | … | |
| qn | qt | … | qz | … | qk | qn | bk | … | b1 | … | bl |
а их совмещение есть автоматная таблица
| A Q | a1 | ... | aj | ... | am |
| q0 | q2b8 | … | qlbi | … | qpbt |
| … | … | … | … | … | … |
| qi | q4b7 | … | qrbl | … | qmbr |
| … | … | … | … | … | … |
| qn | qtbk | … | qzb1 | … | qkbl |
2. Диаграмма автомата.
Диаграмма автомат – ориентированный граф, вершинам которого взаимно - однозначно соответствуют элементы Q, а дугам приписаны некоторые множества пар вида <aibj>, ai Î A bj Î B. Функции d и l определяются следующим образом: d(qlai)=qr, l(qlai)=bj, если ребру, исходящему из вершины ql, приписана пара <aibj> и эта дуга ведет в вершину qr.
Пример: Пусть задана автоматная таблица
| A Q | a1 | a2 |
| q0 | q0b2 | q1b2 |
| q1 | q1b1 | q0b2 |
Соответствующая диаграмма имеет вид:
Замечание: Этот орграф (без bi) есть регулярная грамматика 
.
3. Матрица переходов (соединений).
Матрица переходов представляет собой квадратную матрицу размера 
, в который номера строк и столбцов соответствуют элементам множеств внутренних состояний Q. Клетка матрицы на пересечении i-той строки и j-того столбца заполняется дизъюнкцией пар «вход-выход», которая приписана дуге графа, исходящей из i-той вершины в j-тую вершину. При отсутствии такой ветви клетка заполняется нулем или остается свободной. Так для рассмотренного выше примера имеем:
| Q Q | q0 | q1 |
| q0 | a1b2 | a2b2 |
| q1 | a2b2 | a1b1 |
Лекция №6.
Поведение КА
Продолжительность: 2 часа (90) минут
Ключевые (основные) вопросы (моменты)
Текст лекции
Дата добавления: 2015-12-01; просмотров: 21 | Нарушение авторских прав