Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Тема 6. Эквивалентные состояния автомата и их свойства.






 

Рассмотрим следующую модель. Автомат А последовательно находится в различных состояниях si и sj. И в том, и в другом случае на вход автомата подается входной сигнал x, на выходе формируется сигнал y (рис. 6.1). Возможно ли отличить состояния si и sj одно от другого? Вопрос разрешается при введении понятия эквивалентных состояний КА, о которых ранее уже упоминалось.

 

 

Рис. 6.1. Модель КА в двух различных состояниях.

 

Введем некоторые базовые определения.

Определение 1. Два состояния si и sj автомата А называются 1-эквивалентными, если при подаче на вход автомата одного и того же входного сигнала x реакция автомата, т.е. выходной сигнал y, будет одной и той же независимо от того, находится ли А в состоянии si или в состоянии sj.

Определение 2. Два состояния si и sj автомата А называются 1-различимыми, если при подаче на вход автомата одного и того же входного сигнала x реакция автомата (y) будет разной в зависимости от того, находится А в состоянии si или в состоянии sj.

Определение 3. Два состояния si и sj автомата А называются k-эквивалентными, если при воздействии на автомат одной и той же последовательностью входных сигналов длиной k автомат выдает одну и ту же выходную последовательность независимо от того, находится ли А в состоянии si или в состоянии sj.

Определение 4. Два состояния si и sj автомата А называются k-различимыми, если при воздействии на автомат одной и той же последовательностью входных сигналов длиной k реакция автомата будет представлять собой различные выходные последовательности в зависимости от того, находится А в состоянии si или в состоянии sj.

Определение 5. Два состояния si и sj автомата А называются (просто) эквивалентными, если при воздействии на автомат одной и той же произвольной последовательностью входных сигналов из множества X реакция автомата будет одинаковой вне зависимости от того, в каком состоянии находится автомат – si или sj.

Определение 6. Два состояния si и sj автомата А называются (просто) различимыми, если при воздействии на автомат одной и той же произвольной последовательностью входных сигналов из множества X реакция автомата будет различной в зависимости от того, в каком состоянии находится автомат – si или sj.

Примечание. В контексте определений 1 – 6 можно говорить об эквивалентности или различимости состояний si и sj разных автоматов, т.е. когда si Î S1, sj Î S2, где S1 и S2, – множества состояний автоматов A1 и A2 соответственно.

 

Рассмотрим свойства эквивалентных состояний и продолжим ряд определений.

Свойство 1 (лемма). Если два состояния КА являются k-эквивалентными, то они будут и m-эквивалентными для каждого m £ k.

Доказательство. От противного. Пусть состояния КА si и sj k-эквивалентны, но m‑ различимы (m £ k). Тогда существует входная последовательность длиной m, на которой si отличается от sj. Но в таком случае si и sj будут различимы и при входной последовательности длиной k, т.е. si и sj являются k-различимыми, что противоречит условию леммы. Следовательно, предположение неверно, и si и sj m-эквивалентны. ▄

Свойство 2 (лемма). Если два состояния КА являются k-различимыми, то они будут и m‑ различимыми для каждого m ³ k.

Доказательство. Аналогично предыдущему или по свойству 1: пусть si и sj k‑ различимы, но m-эквивалентны (m ³ k). Однако на основании свойства 1, если два состояния m-эквивалентны, то они должны быть и k-эквивалентны, так как k £ m. Полученное противоречие доказывает справедливость леммы. ▄

Определение 7. Состояние, в которое переходит КА из состояния si при подаче входной последовательности длиной k, называют k-тым преемником si по отношению к данной входной последовательности.

В частном случае, нулевым преемником состояния si является само si.

 

Представляет интерес так называемое разбиение множества состояний КА на классы по следующим правилам:

1) все состояния, принадлежащие одному классу, должны быть k-эквивалентными;

2) все состояния, принадлежащие разным классам, должны быть k-различимыми.

Определение 8. Разбиение множества S состояний КА на классы в соответствии с правилами 1) и 2) называется k-эквивалентным разбиением автомата и обозначается Pk.

Определение 9. Классы k-эквивалентного разбиения автомата называются классами k‑ эквивалентности и обозначаются Σ k1, Σ k2, …

Определение 10. Состояния КА, принадлежащие одному и тому же классу k‑ эквивалентности Σ ki, называются смежными, а принадлежащие разным классам – разобщенными.

Замечание. Ни одно из состояний КА не может принадлежать одновременно двум разным классам k-эквивалентности, так как это означало бы k-различимость состояния самому себе. Следовательно, суммарное число состояний в k-эквивалентном разбиении Pk равно мощности множества состояний КА:

 
 

 

 


Свойство 3 (лемма). k-эквивалентное разбиение автомата единственно.

Доказательство. От противного. Пусть k-эквивалентное разбиение Pk состоит из классов k‑ эквивалентности:

Pk = {Σ k1, Σ k2, …, Σ km}.

Пусть Pk не единственно. Тогда существует другое, альтернативное k-эквивалентное разбиение Pk того же автомата:

 

Пусть Σ kj Î Pk, Σ kj = {sj1, sj2, …, sjd}.

Так как каждое состояние, входящее в Σ kj, k‑ эквивалентно любому другому состоянию из этого же класса и не существует ни одного состояния вне Σ kj , которое было бы k-эквивалентно хотя бы одному состоянию в Σ kj, то в альтернативном разбиении Pk должен быть класс эквивалентности Σ ki, включающий те же состояния, что и Σ kj, и не содержащий никаких других состояний:

 
 


Предположив получим, что каждому классу в Pk соответствует идентичный класс в Pk. Так как суммарное число состояний в Pk такое же, как в Pk, то

 
 

 


то есть k-эквивалентное разбиение автомата является единственным. ▄

Свойство 4 (лемма). Состояния КА, являющиеся разобщенными в Pk, должны быть разобщенными и в (k+1)-эквивалентном разбиении Pk+1.

Доказательство следует из свойства 2.

Свойство 5 (лемма). Если КА имеет два различимых, но k-эквивалентных состояния, то он также имеет два состояния k-эквивалентных, но (k+1)-различимых.

Доказательство: из свойства 2.

Определение 11. k-эквивалентное разбиение автомата А называется (просто) эквивалент­ным разбиением, если во всех классах этого разбиения смежные состояния эквивалентны.

Обозначение: Pэкв.

Определение 12. Каждый класс, входящий в эквивалентное разбиение, называется классом эквивалентности.

Обозначение: Σ 1, Σ 2, …

Таким образом, Pэкв = {Σ 1, Σ 2, …, Σ m}. Эквивалентное разбиение является наиболее детальным разбиением автомата. Оно может быть получено итерационно путем построения k-эквивалентных разбиений при k = 1, 2, 3 и т.д. При совпадении очередного разбиения Pi с предыдущим Pi-1 имеем Pэкв. Очевидно, для эквивалентного разбиения автомата с n состояниями потребуется не более (n-1) итерации.

Примечание. Понятия эквивалентных состояний и эквивалентного разбиения позволяют ввести понятие эквивалентных автоматов. Два автомата А1 и А2 называют эквивалентными, если каждому состоянию si автомата А1 соответствует, по крайней мере, одно эквивалентное ему состояние автомата А2 и, обратно, каждому состоянию sj автомата А2 сопоставимо хотя бы одно эквивалентное ему состояние автомата А1. В противном случае автоматы А1 и А2 называют различимыми.