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

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

Рис. 8

Рис.9

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

Рис.10.

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

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

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

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

Рис.11

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

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

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

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

Рис.12

Теорема:

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

Док-во:

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

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

K’ = K È{p / (q, l) ├* (p, l)& pÎK}

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

Пример. Пусть автомат представлен диаграммой на рис. 13а. Объединим по правилу 1 упрощения автоматов с l-переходами состояния 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) = Æ