Теория и реализация языков программирования



игровой автомат Book Of Ra книга ра онлайн без регистрации. |

Конечные автоматы


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

  1. Q - конечное множество состояний,
  2. T - конечное множество допустимых входных символов (входной алфавит),
  3. D - функция переходов (отображающая множество
    Q \times (T \cup \{e\})
    во множество подмножеств множества Q), определяющая поведение управляющего устройства,
  4. q_0 \in Q
    - начальное состояние управляющего устройства,
  5. F \subseteq Q
    - множество заключительных состояний.

Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис. 3.2.).

Недетерминизм автомата заключается в том, что, во- первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e.


Рис. 3.2. 

Пусть M = (Q, T, D, q0, F) - НКА. Конфигурацией автомата M называется пара

(q, w) \in Q \times T^*
, где q - текущее состояние управляющего устройства, а w - цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него. Конфигурация (q0, w) называется начальной, а конфигурация (q, e), где
q \in F
- заключительной (или допускающей). Тактом автомата M называется бинарное отношение
\vdash
, определенное на конфигурациях M следующим образом: если
p \in D(q, a)
, где
a 2\in T \cup \{e\}, \; \text{то} \; (q, aw) \vdash (p, w)
для всех
w 2\in T^*
.

Будем обозначать символом

\vdash^+ (\vdash^*)
транзитивное (реф- лексивно-транзитивное) замыкание отношения
\vdash
. Будем говорить, что автомат M допускает цепочку w, если
(q_0, w) \vdash^* (q, e)
для некоторого
q \in F
. Языком, допускаемым, (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество входных цепочек, допускаемых автоматом M. То есть,

L(M)=\{w \mid w \in T^* \; \text{и} \; (q_0,w) \vdash^* (q,e) \; \text{для некоторого} \; q \in F \}

Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние и не может делать переходы по e.




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