Локальные автоматы

Определение:

Граф Майхилла [math]G[/math] (над алфавитом [math]\Sigma[/math]) (англ. Myhill graph) — ориентированный граф, удовлетворяющий свойствам: 1. Для каждой упорядоченной пары вершин [math]v[/math] и [math]u[/math] существует только одно ребро из [math]v[/math] в [math]u[/math]. 2. Некоторые вершины обозначены начальными, а некоторые — конечными. Ребро может одновременно быть начальным и конечным. 3. Вершины обозначены различными символами из конечного алфавита [math]\Sigma[/math], то есть мы можем обращаться к вершине по ее символу.

Рисунок 1

Рисунок 2

Рассмотрим пример (рис. 1). Этот граф может быть использован для распознавания строк над алфавитом [math]\Sigma = \{a, b\}[/math]. По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на [math]a[/math]; он имеет вид: [math]L = (a \Sigma^* \cap \Sigma^* a) \setminus \Sigma^* b^2 \Sigma^*[/math].

Пусть [math]G[/math] — граф Майхилла над алфавитом [math]\Sigma[/math].

Символ [math]c \in \Sigma[/math] назовем разрешенным, если им помечена вершина, являющая одновременно начальной и конечной.

Не пустая строка [math]c_1c_2...c_n[/math] из [math]\Sigma^*[/math] длиной не менее двух символов, называется разрешенной, если символом [math]c_1[/math] отмечена стартовая вершина, а символом [math]c_n[/math] — конечная, и для всех [math]1 \leqslant i \leqslant n - 1[/math] в [math]G[/math] существует ребро [math]a_i \rightarrow a_{i+1}[/math].

Язык [math]L(G)[/math], распознаваемый графом Майхилла, состоит из всех разрешенных строк из [math]\Sigma^+[/math].

Рассмотрим детерменированный конечный автомат, представленный на рисунке 2. Не сложно проверить, что он распознает тот же язык, что и граф на рисунке 1.

Покажем, графы Майхилла могут быть представлены в виде автоматов. Пусть [math]A = (S, \Sigma, i, \delta, T)[/math] — ДКА.

Определение:

Автомат [math]A[/math] называется локальным (англ. local automation), если для любого [math]c[/math] из [math]\Sigma[/math] множество [math]\{\delta(s, c): s \in S\}[/math] содержит не более одного элемента.

Определение:

Автомат [math]A[/math] называется стандартным локальным автоматом (англ. standard loal automation), если в нем нет перехода в начальное состояние.

Таким образом, автомат является локальным, если для каждого [math]c[/math] из [math]\Sigma[/math] нет переходов, отмеченных [math]c[/math], или если все они ведут в одно состояние.

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

Теорема:

Язык распознается графом Майхилла тогда и только тогда, когда он распознается стандартным локальным автоматом, стартовое состояние которого не является терминальным.

Доказательство:

[math]\triangleright[/math]

[math]\Rightarrow[/math] Пусть [math]G[/math] — граф Майхилла. Построим автомат [math]A[/math] следующим образом: Добавим вершину [math]\Diamond[/math] в [math]G[/math] с ребрами от [math]\Diamond[/math] к каждой стартовой вершине [math]G[/math]; отметим вершину [math]\Diamond[/math] как стартовое состояние. Отметим конечные вершины как терминальные состояния. Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает. Переходы преобразуются следующим образом: По построению стартовое состояние не является терминальным. Покажем, что полученный автомат конечен. Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате. Если мы рассмотрим любое другое состояние [math]s[/math], то два перехода из [math]s[/math] могут иметь одинаковые метки только в том случае, если в [math]G[/math] оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойтсву 1. То есть [math]A[/math] — ДКА, возможно, незаконченный. По построению он является стандартным локальным автоматом. Теперь просто проверить, что [math]L(A) = L(G)[/math]. [math]\Leftarrow[/math] Пусть [math]A = (S, \Sigma, i, \delta, T)[/math] — стандартный локальный автомат, стартовое состояние которого не является терминальным. Построим по нему граф Майхилла следующим образом: Отметим все состояния [math]A[/math], кроме стартового, [math]input[/math] символами, стоящими на ребрах, входящих в эти состояния. Сотрем все метки на ребрах [math]A[/math]. Отметим все состояния [math]s[/math] как начальные вершины, если существует переход из [math]i[/math] в [math]s[/math] Отметим все терминальные состояния как конечные вершины. Удалим вершину [math]i[/math] и все ребра, исходящие из нее. Назовем полученный граф [math]G[/math] — он будет графом Майхилла по построению. Легко проверить, что [math]L(G) = L(A)[/math].

[math]\triangleleft[/math]