Э квивалентность системы автоматов.

Два состояния _i и _j автоматов М₁ и М₂ называют эквивалентными друг другу состояниями, если при поступлении на вход автоматов любых последовательностей E_m, поступивших на вход М₁/_i и М₂/_j, реакции автоматов оказались совпадающими.

Два состояния _i и _j автоматов М₁ и М₂ называются различимыми состояниями, если найдется хотя бы одна входная последовательность E_m такая, что при ее поступлении на вход М₁/_i и М₂/_j, реакции оказываются различимыми (отличимыми друг от друга).

Два состояния автоматов _i и _j являются различимыми состояниями, если строки _i и _j в подтаблице реакций оказываются отличными друг от друга. Такие системы называются явно различимыми.

Два состояния _i и _j являются эквивалентными друг другу состояниями, если строки _i и _j в полной таблице переходов либо лексико-графически совпадают, либо становятся таковыми после замены _i на _j и наоборот (такие состояния называются явно эквивалентными).

k-эквивалентное состояние автомата.

Два состояния _i и _j автомата M называются k-эквивалентными друг другу состояниями, если при поступлении на вход состояния M/_i и M/_j любых входных последовательностей E_k реакции автоматов совпадают.

Два состояния _i и _j автомата M называются k-различимыми состояниями, если найдется хотя бы одна входная последовательность E_k, что при ее поступлении на вход автомата M/_i и M/_j реакции оказываются отличными друг от друга.

Лемма:

1⁰ Два состояния _i и _j l-эквивалентны, если они k­-эквивалентны, при l ≤ k.

2⁰ Два состояния _i и _j l-различимы, если они k-различимы, при k ≤ l.

Доказательство 1⁰:

От обратного: состояния _i и _j k-эквивалентны, но l-различимы.

т.к. l ≤ k, то E_k = E_l + E_{k – l}, тогда они k-различимы, что неверно из условия леммы.

Доказательство 2⁰:

От обратного: состояния _i и _j k-различимы, но l-эквивалентны, тогда по лемме 1⁰ они k- эквивалентны, что неверно из условия леммы.

k-эквивалентным разбиением состояния автомата (P_k) называют множество классов P_k = {Σ₁^k, Σ₂^k,…, Σ_m^k}, где каждый класс Σ_i^k, является совокупностью всех k-эквивалентных состояний.

Σ_i^k = { _i1^k, _i2^k,…, _il^k }

S = Σ₁^k  Σ₂^k  …  Σ_m^k, Σ_i^k  Σ_j^k =  (условия разбиения)

Лемма:

1⁰ Каждое состояние k-эквивалентно самому себе _i^k = _i^k

2⁰ Если состояние _il^k k-эквивалентно состоянию _im^k _il^k = _im^k  то и состояние _im^k k- эквивалентно состоянию _il^k _im^k = _il^k.

_i1 и _i2 - называются смежными состояниями, если они принадлежат Σ_i^k (_i1  Σ_i^k, _i2  Σ_i^k).

Если _i1  Σ_i^k, а _i2  Σ_j^k ( Σ_i^k ≠ Σ_j^k) , то такие состояния называют разобщенными состояниями.

Теорема:

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

Доказательство:

От обратного:

P`<sub>k</sub> = {Σ`₁^k, Σ`<sub>2</sub><sup>k</sup>,…, Σ`_m^k}

P_k = {Σ₁^k, Σ₂^k,…, Σ_m^k}

Рассмотрим _i  S, пусть _i  Σ_i^k и _i  Σ`_r^k, но по определению каждое состояние содержит все k- эквивалентные состояния, т.е.

Σ_i^k = { _i1^k, _i2^k,…, _il^k }

Σ`<sub>r</sub><sup>k</sup> = { <sub>i1</sub><sup>k</sup>, <sub>i2</sub><sup>k</sup>,…, <sub>il</sub><sup>k</sup> }  Σ<sub>i</sub><sup>k</sup> = Σ`_r^k – совпадают  P_k = P`_k также совпадают.

Если в k-эквивалентном разбиении состояний автомата P_k в одном из его классов Σ_i^k найдется хотя бы одна пара состояний _im^k и _jl^k k-эквивалентные, но вообще говоря различимые, то P_{k + 1} разбиение состояния автомата образуется путем собственного разделения P_k-эквивалентного разбиения.

Лемма:

Если в каком-то из классов Σ_i^k k-эквивалентного разбиения состояний автомата найдется хотя бы одна пара состояний _im^k и _jl^k k-эквивалентные, но вообще говоря различимые, то в каком-то из классов Σ_j^k найдется пара состояний _in^k и _jp^k, которые являются k-эквивалентными и (k + 1)- различимыми.

Доказательство:

_im^k и _jl^k найдем входную последовательность при которой реакции различны: пусть {E¹}, {E²}, …,{E^{k - 1}}-эквивалентные, а Е^k – исходная, т.е. она приводит к отличным друг от друга реакциям. Е^k = {E_v1, E_v2, …, E_{vq – (k + 1)}, …, E_vq}

Лемма 1:

Для нетривиального автомата при P_k ≠ P_{k – 1} число классов не меньше ( k + 1), т.е. | P_k |  k + 1.

Доказательство:

От обратного: | P_k | = k  | P₁ | = 1, т.е. P₁ = {Σ₁¹}, иными словами все состояния автомата одноэквивалентны друг другу, т.е. Σ₁¹ = S.

_i и _j – эквивалентны друг другу, но _i и _j любые  все состояния эквивалентны друг другу: поведение не зависит от пост. Последовательности  автомат тривиальный  | P₁ | > 1 – имеет хотя бы два класса, тогда:

| P₁ |  2

| P₂ |  3

:

| P_k |  k + 1 и т.д.

Лемма 2:

Для нетривиального автомата для P_k ≠ P_{k – 1}, число состояний в каждом из классов не больше ( n – k), т.е. | Σ_i^k | ≤ n – k.

Доказательство:

От обратного: пусть | Σ_i^k | = n – k + 1, | P_k | = k + 1, | Σ_j^k | = 1, j ≠ i, тогда:

| Σ₁^k | + … + | Σ_{i - 1}^k | + | Σ_i^k | + | Σ_{i +1}^k | + … + | Σ_{k + 1}^k | = 1 + … + 1 + ( n – k + 1) + 1 + … + 1 = k + (n – k + 1) = n + 1 > n = | S |  утверждение ошибочно.

Лемма 3:

Для нетривиального автомата P_n = P_{n – 1}.

Доказательство:

От обратного: P_n ≠ P_{n – 1}, | P_n |  n + 1 > | S | = n  процесс закончиться на P_{n – 1} шаге.

Теорема:

Два состояния автомата _i и _j эквивалентны, если они ( n – 1 ) – эквивалентны. (Доказательство следует из леммы 3.)