7.3. Квазиэквивалентные автоматы

Говорят, что состояние автомата М квазиэквивалентно состоянию автомата М, если любая входная последовательность, допустимая для вызывает одинаковые реакции при приложении ее к и Говорят, что автомат М квазиэквивалентен автомату М, если для каждого состояния автомата М имеется, по крайней мере, одно состояние автомата М, такое, что квазиэквивалентно На основе этого определения автомат может быть интерпретирован следующим образом. Если дан неизвестный автомат, который может быть М или М, и известна реакция этого автомата на любую входную последовательность, допустимую для некоторого состояния автомата М, то нет способа определить, является неизвестный автомат автоматом М или М. Таким образом, М квазиэквивалентен М, если не существует способа отличить М от М при помощи внешних экспериментов, которые используют только те входные последовательности, которые допустимы для состояний автомата М. Заметим, что отношение квазиэквивалентности не является симметричным отношением; тот факт, что М квазиэквивалентен М, не означает, что М квазиэквивалентен М.

Пусть — множества состояний автомата М такие, что каждое состояние автомата М включено, по крайней мере, в одно множество Множество множеств называется группировкой, n называется мощностью группировки. Два состояния, которые находятся вместе, по крайней

мере, в одном множестве , составляют сопряженную пару; пара состояний, которая не является сопряженной, называется разобщенной парой. Группировка называется правильной, если она удовлетворяет двум следующим условиям: (1) реакции автомата УН где и составляют любую сопряженную пару, на любой входной символ допустимый для и одинаковы; (2) первые преемники состояний и по отношению к одинаковы или составляют сопряженную пару.

Пусть автомат М имеет множество состояний Пусть автомат М квазиэквивалентен автомату М и имеет множество состояний По определению квазиэквивалентности каждому состоянию автомата М должно соответствовать, по крайней мере, одно состояние автомата М, которое квазиэквивалентно Распределим состояния автомата М по множествам таким, что — множество всех состояний, по отношению к которым о квазиэквивалентно. Эти множества составляют группировку, так как они включают каждое состояние М, по крайней мере, один раз. Пусть — произвольная пара состояний из и пусть — любой символ, допустимый для Реакция должна быть такой же, как и реакция Поэтому реакции должны быть одинаковы. Предположим, что первыми преемниками состояний по отношению к являются и что первый преемник состояния по отношению к есть Так как квазиэквивалентно должно быть квазиэквивалентно Поэтому не могут быть разобщенными и должны принадлежать одному и тому же множеству В заключение можно сделать вывод, что группировка автомата М, построенная описанным выше способом, должна быть правильной группировкой.

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

Если состояние M, принадлежащее множеству переходит в состояние, принадлежащее множеству , и при этом выдается выходной символ при входном символе то в М! состояние переходит в и при этом выдается выходной символ при приложении входного символа Никакой неоднозначности при таком построении не получается, так как, если некоторое состояние автомата М, принадлежащее , переходит в некоторое состояние, принадлежащее и при этом выдается выходной символ на входной символ то каждое состояние М, которое принадлежит и для которого допустим символ переходит в состояние, которое принадлежит и при этом выдается символ на входной символ Из построения следует, что состояние автомата квазиэквивалентно каждому состоянию М, принадлежащему множеству . Поэтому автомат М квазиэквивалентен автомату М. Таким образом, имеем следующий результат.

Теорема 7.1. Каждому автомату с n состояниями, который квазиэквивалентен автомату М, соответствует в М правильная группировка мощности . Каждой правильной группировке мощности n в автомате М соответствует автомат М, который квазиэквивалентен автомату М.

Построение правильной группировки автомата М при заданном М и построение М при заданной правильной группировке автомата М можно осуществить так, как это описано выше. Если М — автомат с r состояниями и если то говорят, что М — сокращенная форма М. Если не существует сокращенной формы М, имеющей меньше чем n состояний, то говорят, что — минимальная форма М, которая обозначается М. Минимальная форма М данного автомата М имеет такое же значение для автоматов с ограничениями на входе, как и для автоматов без ограничений на входе: М — наименьший автомат, который ведет себя так же, как заданный автомат М. Однако следует иметь в виду, что в случае автомата с ограничениями на входе поведение автоматов М и М сравнимо только в отношении входных последовательностей, допустимых для состояний исходного автомата М.

Теорема 7.1 предполагает, что автомат М может быть определен из автомата состояниями посредством перечисления всех правильных группировок автомата М, имеющих мощность r или меньше, и выбора из них наименьшей. Если задана наименьшая правильная группировка, или минимальная правильная группировка, то автомат, квазиэквивалентный автомату М, может всегда быть построен описанным ранее способом; этот автомат является минимальной формой автомата М. Хотя этот метод и дает решение, он очень трудоемок во всех случаях, кроме наиболее тривиальных, поскольку требует перечисления правильных группировок. В следующем параграфе будет получен ряд результатов, которые позволят отчасти облегчить задачу такого перечисления.