Автоматы с  - переходами.

Автоматы с - переходами естественно возникают в различных приложениях, и позволяют представить любой автомат в виде двухполюсников с одним входом и одним выходом, а так же строить сети из таких автоматов, сохраняя в них единственный вход и единственный выход. От рассмотренных ранее автоматов они отличаются тем, что в них присутствуют переходы, осуществляемыми без чтения входной цепочки ( на диаграмме такие переходы обозначаются стрелками, помеченными символом).

Рис. 8

Рис.9

Например, рассмотрим автомат с двумя выходами, представленный на рис. 9. Он имеет два выхода. Если просто объединить две выходные вершины, то получившийся автомат не будет эквивалентен исходному, т.к. после построения символа bв результирующем автомате возможно будет построение символов а, что было невозможно в исходном автомате. Эквивалентный исходному автомат представлен на рис. 10.

Рис.10.

Иногда в двухполюснике конечные состояния изображаются как

Очевидно, что если L– А-язык, то ему можно сопоставить двухполюсник.

Пусть языкам L₁иL₂сопоставлены соответствующие двухполюсники

(рис.11 а). Тогда их объединению, конкатенации и итерации языка L₁ будут, соответственно, сопоставлены двухполюсники рис. 11б, 11в, 11г

Рис.11

Т.о. доказана теорема: Класс А-языков замкнут относительно операций объединения, конкатенации и итерации.

Оптимизация автоматов с -переходами.

Если из состояния А исходит единственная дуга и это -дуга в состояние В, то вершины А и В можно слить.

Если из вершины А выходит -дуга в вершину В, являющуюся начальной вершиной некоторой дуги( не петли) или последовательности дуг, а С – конечная вершина этой дуги (последовательности дуг), и единственная дуга из С --дуга в вершину А, то вершины А,В и С можно слить (примеры такого слияния приводятся на рис. 12 ( для одной дуги – а, б; для последовательности – в, г).

Рис.12

Теорема:

Классы языков, допускаемых детерминированными автоматами и автоматами с -переходами, совпадают.

Док-во:

Пусть автомат А = <Q,V_T,q₀,F,K> - автомат-переходами. Построим соответствующий детерминированный автоматА’= <Q’,V_T,q₀’,F’,K’>, такой, чтоL(A)=L(A’) следующим образом.

F’(q,a)={p / (q,ax) ├⁺ (p,x)}

K’ = K {p / (q, ) ├* ( p, )& pK}

Несложно показать, с использованием математической индукции по числу символов в распознаваемой цепочке, что получаемый таким образом автомат А’ переходит при распознавании цепочки Х в конечное состояние тогда и только тогда, когда существует последовательность переходов в конечное состояние автомата А при распознавании этой же цепочки символов.

Пример. Пусть автомат представлен диаграммой на рис. 13а. Объединим по правилу 1 упрощения автоматов с -переходами состояния 4 и 5 и переобозначим состояния, как показано на рис. 13б.

Построим функцию переходов детерминированного автомата А’.

F(A, a) = [B,C, D, F] F(A, b) = [E] F(A,c) = 	F([B, C, D, F], a) = [C,D, F], F([B, C, D, F], b) = [D, E], F([B, C, D, F], c) = ,	F([E], a) = , F([E], b) = , F([E], c) = [D],
F([C, D, F], a) = [C, D, F] F([C, D, F], b) = [E] F([C, D, F],c) = 	F([D, E], a) = [D, F] F([D, E], b) = [E] F([D, E],c) = [D]	F([D, F], a) = [D, F] F([D, F], b) = [E] F([D, F], c) = 
F([D], a) = [D, F] F([D], b) = [E] F([D], c) = 

K’ = { [B, C, D, F] , [ D, F], [C, D, F]}

Диаграмма детерминированного автомата представлена на рис. 14.

Рис.14

Тот же автомат после переобозначения состояний представлен на рис. 15.

Рис.15