Изменения
Нет описания правки
Известно, как по регулярному выражению построить автомат с эпсилон<tex>\varepsilon</tex>-переходами, но потом его нужно перобразовать к детерминированному конечному автомату (ДКА). Изучим, как по регулярному выражению сразу построить ДКА.
==Графы Майхилла.==
{{Определение|definition='''Граф Майхилла G (над алфавитом А) ''' (англ. ''Myhill graph'') {{--- }} ориентированный граф, удовлетворяющий свойствам:
1. Для каждой упорядоченной пары вершин v1 и v2 существует только одно ребро из v1 в v2.
2. Некоторые вершины обозначены начальными, а некоторые - конечными. Ребро может одновременно быть начальным и конечным.
3. Вершины обозначены различными символами из конечного алфавита А, то есть мы можем обращаться к вершине по ее символу.
}}
Пусть G {{- --}} граф Майхилла над алфавитом А.
Символ а из А называется назовем разрешенным, если им помечена вершина, являющая одновременно начальной и конечной.
Не пустая строка a_1a_2...a_n из A* длиной не менее двух символов, называется разрешенной, если символом a_1 отмечена стартовая вершина, а символом a_n - конечная, и для всех 1 <= i <= n-1 в G существует ребро a_i -> a_{i+1}.
Покажем, графы Майхилла могут быть представлены в виде автоматов.
Пусть A M = (S, A, i, delta, T) {{--- }} ДКА, не обязательно законченный. {{Определение|definition= Автомат M называется '''локальным''' (англ. '''local automation'''), если для любого a из A множество {s * a: s in S} содержит не более одного элемента. }}
Таким образом, автомат является локальным, если для каждого а из А нет переходов, отмеченных а, или если все они в одно состояние.
Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится.
{{Теорема. |id=th1|statement=Язык распознается графом Майхилла тогда и только тогда, когда он распознается стандартным локальным автоматом, стартовое состояние которого не является терминальным.Доказательство.|proof=
(->)
Пусть G - граф Майхилла.
* Удалим вершину i и все ребра, исходящие из нее.
Назовем полученный граф G - он будет графом Майхилла по построению. Легко проверить, что L(G) = L(A).
}}
