Мура Мили
Z |
0 |
1 |
1 |
1 |
1 |
0 |
X \ S` |
`10 |
`11 |
`12 |
`20 |
`21 |
`22 |
1 |
`11 |
`10 |
`12 |
`12 |
`11 |
`10 |
2 |
`21 |
`20 |
`22 |
`22 |
`21 |
`20 |
S\X |
Z v |
S v + 1 |
||
1 |
2 |
1 |
2 |
|
`10 |
1 |
1 |
`11 |
`21 |
`11 |
0 |
1 |
`10 |
`20 |
`12 |
1 |
0 |
`12 |
`22 |
`20 |
1 |
0 |
`12 |
`22 |
`21 |
1 |
1 |
`11 |
`21 |
`22 |
0 |
1 |
`10 |
`20 |
P = {0 = { `11, `22 }, 1 = { `10, `21 }, 2 = { `12, `20 }}
S\X |
Z v |
S v + 1 |
|||
1 |
2 |
1 |
2 |
||
0 |
0 |
1 |
1 |
2 |
|
1 |
1 |
1 |
0 |
1 |
|
2 |
1 |
0 |
2 |
0 |
|
Задача 3:
пусть требуется описать автомат, который управляет кодовым замком (код 773).
X` = { 0, 1,…, 9, C } X = { 7, 3, C, }
Z = { 0, 1 }
S = { 0 = «С», 1 = «С7», 2 = «С77», 3 = «С» }
S \ X |
Z v |
S v + 1 |
||||||
7 |
3 |
|
С |
7 |
3 |
|
С |
|
0 |
0 |
0 |
0 |
0 |
1 |
3 |
3 |
0 |
1 |
0 |
0 |
0 |
0 |
2 |
3 |
3 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Э квивалентность системы автоматов.
Два состояния i и j автоматов М1 и М2 называют эквивалентными друг другу состояниями, если при поступлении на вход автоматов любых последовательностей Em, поступивших на вход М1/i и М2/j, реакции автоматов оказались совпадающими.
Два состояния i и j автоматов М1 и М2 называются различимыми состояниями, если найдется хотя бы одна входная последовательность Em такая, что при ее поступлении на вход М1/i и М2/j, реакции оказываются различимыми (отличимыми друг от друга).
Два состояния автоматов i и j являются различимыми состояниями, если строки i и j в подтаблице реакций оказываются отличными друг от друга. Такие системы называются явно различимыми.
Два состояния i и j являются эквивалентными друг другу состояниями, если строки i и j в полной таблице переходов либо лексико-графически совпадают, либо становятся таковыми после замены i на j и наоборот (такие состояния называются явно эквивалентными).
k-эквивалентное состояние автомата.
Два состояния i и j автомата M называются k-эквивалентными друг другу состояниями, если при поступлении на вход состояния M/i и M/j любых входных последовательностей Ek реакции автоматов совпадают.
Два состояния i и j автомата M называются k-различимыми состояниями, если найдется хотя бы одна входная последовательность Ek, что при ее поступлении на вход автомата M/i и M/j реакции оказываются отличными друг от друга.
Лемма:
10 Два состояния i и j l-эквивалентны, если они k-эквивалентны, при l ≤ k.
20 Два состояния i и j l-различимы, если они k-различимы, при k ≤ l.
Доказательство 10:
От обратного: состояния i и j k-эквивалентны, но l-различимы.
т.к. l ≤ k, то Ek = El + Ek – l, тогда они k-различимы, что неверно из условия леммы.
Доказательство 20:
От обратного: состояния i и j k-различимы, но l-эквивалентны, тогда по лемме 10 они k- эквивалентны, что неверно из условия леммы.
k-эквивалентным разбиением состояния автомата (Pk) называют множество классов Pk = {Σ1k, Σ2k,…, Σmk}, где каждый класс Σik, является совокупностью всех k-эквивалентных состояний.
Σik = { i1k, i2k,…, ilk }
S = Σ1k Σ2k … Σmk, Σik Σjk = (условия разбиения)
Лемма:
10 Каждое состояние k-эквивалентно самому себе ik = ik
20 Если состояние ilk k-эквивалентно состоянию imk ilk = imk то и состояние imk k- эквивалентно состоянию ilk imk = ilk.
i1 и i2 - называются смежными состояниями, если они принадлежат Σik (i1 Σik, i2 Σik).
Если i1 Σik, а i2 Σjk ( Σik ≠ Σjk) , то такие состояния называют разобщенными состояниями.
Теорема:
k-эквивалентное состояние автомата единственно с точностью до обозначения.
Доказательство:
От обратного:
P`k = {Σ`1k, Σ`2k,…, Σ`mk}
Pk = {Σ1k, Σ2k,…, Σmk}
Рассмотрим i S, пусть i Σik и i Σ`rk, но по определению каждое состояние содержит все k- эквивалентные состояния, т.е.
Σik = { i1k, i2k,…, ilk }
Σ`rk = { i1k, i2k,…, ilk } Σik = Σ`rk – совпадают Pk = P`k также совпадают.
Если в k-эквивалентном разбиении состояний автомата Pk в одном из его классов Σik найдется хотя бы одна пара состояний imk и jlk k-эквивалентные, но вообще говоря различимые, то Pk + 1 разбиение состояния автомата образуется путем собственного разделения Pk-эквивалентного разбиения.
Лемма:
Если в каком-то из классов Σik k-эквивалентного разбиения состояний автомата найдется хотя бы одна пара состояний imk и jlk k-эквивалентные, но вообще говоря различимые, то в каком-то из классов Σjk найдется пара состояний ink и jpk, которые являются k-эквивалентными и (k + 1)- различимыми.
Доказательство:
imk и jlk найдем входную последовательность при которой реакции различны: пусть {E1}, {E2}, …,{Ek - 1}-эквивалентные, а Еk – исходная, т.е. она приводит к отличным друг от друга реакциям. Еk = {Ev1, Ev2, …, Evq – (k + 1), …, Evq}
Лемма 1:
Для нетривиального автомата при Pk ≠ Pk – 1 число классов не меньше ( k + 1), т.е. | Pk | k + 1.
Доказательство:
От обратного: | Pk | = k | P1 | = 1, т.е. P1 = {Σ11}, иными словами все состояния автомата одноэквивалентны друг другу, т.е. Σ11 = S.
i и j – эквивалентны друг другу, но i и j любые все состояния эквивалентны друг другу: поведение не зависит от пост. Последовательности автомат тривиальный | P1 | > 1 – имеет хотя бы два класса, тогда:
| P1 | 2
| P2 | 3
:
| Pk | k + 1 и т.д.
Лемма 2:
Для нетривиального автомата для Pk ≠ Pk – 1, число состояний в каждом из классов не больше ( n – k), т.е. | Σik | ≤ n – k.
Доказательство:
От обратного: пусть | Σik | = n – k + 1, | Pk | = k + 1, | Σjk | = 1, j ≠ i, тогда:
| Σ1k | + … + | Σi - 1k | + | Σik | + | Σi +1k | + … + | Σk + 1k | = 1 + … + 1 + ( n – k + 1) + 1 + … + 1 = k + (n – k + 1) = n + 1 > n = | S | утверждение ошибочно.
Лемма 3:
Для нетривиального автомата Pn = Pn – 1.
Доказательство:
От обратного: Pn ≠ Pn – 1, | Pn | n + 1 > | S | = n процесс закончиться на Pn – 1 шаге.
Теорема:
Два состояния автомата i и j эквивалентны, если они ( n – 1 ) – эквивалентны. (Доказательство следует из леммы 3.)