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

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

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

мере, в одном множестве Σ₁, составляют сопряженную пару; пара состояний, которая не является сопряженной, называется разобщенной парой. Группировка называется правильной, если она удовлетворяет двум следующим условиям: (1) реакции автомата М| σ_i1 и M| σ_i2, где σ_i1 и σ_i2 составляют любую сопряженную пару, на любой входной символ ξ_j, допустимый для σ_i1 и σ_i2, одинаковы; (2) первые преемники состояний σ_i1 и σ_i2 по отношению к ξ_j одинаковы или составляют сопряженную пару.

Пусть автомат М имеет множество состояний { σ₁, σ₂,..., σ_n}. Пусть автомат М! квазиэквивалентен автомату М и имеет множество состояний { σ´₁, σ´₂,..., σ´_n}. По определению квазиэквивалентности каждому состоянию σ_i автомата М должно соответствовать, по крайней мере, одно состояние автомата М', которое квазиэквивалентно σ_i. Распределим состояния автомата М по множествам Σ₁, Σ₂,..., Σ_n таким, что Σ_i — множество всех состояний, по отношению к которым σ´_i квазиэквивалентно. Эти множества составляют группировку, так как они включают каждое состояние М, по крайней мере, один раз. Пусть σ_i1 и σ_i2 — произвольная пара состояний из Σ_i и пусть ξ_i — любой символ, допустимый для σ_i1 и σ_i2,. Реакция М| σ_i1 и M| σ_i2, на ξ_i, должна быть такой же, как и реакция М´| σ´_i на ξ_j. Поэтому реакции М| σ_i1 и M| σ_i на ξ_j должны быть одинаковы. Предположим, что первыми преемниками состояний σ_i1 и σ_i2 по отношению к ξ_j являются σ_k1 и σ_k2 и что первый преемник состояния σ_i по отношению к ξ_j есть σ´_k. Так как σ´_i квазиэквивалентно σ_i1 и σ_i2, то σ´_k должно быть квазиэквивалентно σ_k1 и σ_k2. Поэтому σ_k1 и σ_k2 не могут быть разобщенными и должны принадлежать одному и тому же множеству Σ_k. В заключение можно сделать вывод, что группировка Σ₁, Σ₂,..., Σ_n автомата М, построенная описанным выше способом, должна быть правильной группировкой.

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

σ´₁, σ´₂,..., σ´_n. Если состояние М, принадлежащее множеству Σ_u, переходит в состояние, принадлежащее множеству Σ_v, и при этом выдается выходной символ ζ_k при входном символе ξ_j, то в М' состояние σ´_u переходит в σ´_v и при этом выдается выходной символ ζ_k при приложении входного символа ξ_j. Никакой неоднозначности при таком построении не получается, так как, если некоторое состояние автомата М, принадлежащее Σ_k, переходит в некоторое состояние, принадлежащее Σ_v, и при этом выдается выходной символ ζ_k на входной символ ξ_j, то каждое состояние М, которое принадлежит Σ_u и для которого допустим символ ξ_j, переходит в состояние, которое принадлежит Σ_v, и при этом выдается символ ζ_k на входной символ ξ_j. Из построения М´ следует, что состояние σ´_i автомата М' квазиэквивалентно каждому состоянию М, принадлежащему множеству Σ_i. Поэтому автомат М' квазиэквивалентен автомату М. Таким образом, имеем следующий результат.

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

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

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