同調系列をもつ順序機械の諸性質
清 木 泰 弌＊
On Some Properties of Sequential Machines with the Synchronizing Sequence
by
Yasukazu SEIKI
（Electrical Engineering）
Asequential machine has a finite humber of internal states， and its behavior is described by the state transition table． In general， the state transition of a machine by the given input sequence depends on what state it happens to start in，
Asynchronizing sequence， however， always leaves the machine in a specific final state，
regardless of its initial state． The existence of such a synchronizing sequence and the method how to find it have already been known． But any precise definition of synchronization has never been given．
In this paper， the idea of partial synchronizatioll which is related to the subset of given states is introduced in order to establish the fundamental definition of complete synchronization．
By the application of this partial synchronization to machines which have state partitions， some th60rems concerning with complete synchronization of machines with S． P． partitions are obtained．
Furthermore， the error correcting capacity of sequential machines with th6．synchronizing sequence is discussed in the cases that machin6s have， or don t have， S．P． partitions．
1．まえがき
順序機械の動きは，その与えられた状態遷移表によ り完全に規定されている．簡約化された完全な状態遷 移表をもつ機械において初期状態が定まれば，与えら れた入力系列による状態遷移は一義的に表わされる．
ところが，ある機械においては，任意の状態を一様 に，ある定められた状態に遷移せしめるような入力系 列が存在する．このとき，その入力系列による機械の 状態遷移に関しては，常に特定の情報が存在すること になるから，初期状態に関係なく入力系列のみにより 機械の状態遷移を知ることが可能となる．このような 入力系列をsynchronizing sequence（以後，これを 同調系列とよぶことにする）という．同調系列の存在 はすでに知られており，その求め方も与えられている が1），同調系列の明確な定i義や諸性質，特に機械が同 調系列をもつための条件等に関しては，まだ報告され ていないようである．
本論文においては，まず与えられた機械の内部状態
＊電気工学教室
の部分集合に関する部分同調性の概念を導入し，これ に基いて全内部状態の集合に関する完全同調性の基本 的な定義づけを行なった．また，機械の同調性に関す る必要条件として，M（Su， x）＝M（Sv， x）なる同 調状態対（SU， SV）の存在を示した．
さらに，状態分割をもつ順序機械2）の同調性を，特 にSP分割について調べてみた．その結果， SP分割 をもつ機械の完全同調性は， そのSP分割内の状態 ブロックの集合に関する完全同調性と，状態ブロック に関する部分同調性の二つの条件により表わされるこ
とが明らかになった．
最後に，完全同調する機械における状態誤り訂正の 問題を，機械がSP分割をもつ場合およびもたない場 合の各々について論じた．
2．基本定義
順序機械は入力を与えるごとに，逐次その内部状態
を変えていく．一般に，この内部状態の数は有限個で
ある．本論文では，このような有限状態機械における
入力系列と内部状態の関係だけを論ずるため，以下に
定義するような，特定の初期状態，最終状態および出 力をもたないMoore形順序機械を考察の対象とした．
（定義2・1）順序機械4を次の三項系列で表わす．
浸＝（S，Σ，M）
ここに，Sはオの有限個の内部状態の集合，．Σは 入力記号の集合，およびMは次のような状態遷移写像 を表わす．
M：S×。Σ→S
また，入力xεΣによりSiεSがS」εSに遷移する
ことを，
M（Si， x）＝Sjと表わす．
なお，すべてのSiεSに対して常に入力xε。Σによ る状態遷移の値が与えられているものとする．
（定義2・2）5＝｛s1， s2，……s。｝
であるとき，冨1S2…・亙を状態ベクトルという．
任意の状態SiεSに対する状態遷移の値を次のように 表わす．
VsiεS， M（si， x）≡M（sls2……s。， x）・≡
VSi（o）dS， M（Si（o）， x）≡M（S， x）．
（定義2・3）Sの分割πを次のように定義する．
π＝・｛Bπ（1），Bπ（2），……， Bπ（m）｝
ここに，UBπ（i）＝S＆Bπ（i）nB冗（」）＝A i＝1
（Aは空集合を表わす）ただしi≠j，である．
Bπを状態ブロックという．
分割πのあらゆる状態が分割τの状態ブロックに 含まれるときおよびそのときに限り，π≦τと表わす．
また，π，τが各々共通の状態ブロックをもたないと きおよびそのときに限り，π・τ＝Oと表わす．
（定義2・4）2）状態分割πをもつ機械において，
ある状態ブロックB7および入力xに対して，
M（Bて，x）dBノ冗
なるBノπが唯一つ存在する場合およびその場合に限 り，分割πはsubstitαtion property（以後これを SPと略す）をもっという． このπをSP分割とよ
ぶ．
（定義2・5）2） SP分割πをもつ機械オにお
いて，
オπ＝（｛Bπ｝，Σ，Mπ）
なる・4πを浸のπ・image machineという．ここ
に，
M（Bπ，x）qB1π となる場合およびその場合に限り，
M7（Bπ， x）＝B π と表わす．
3．部分同調性と完全同調性
初期状態として， 順序機械の内部状態の部分集合 S（o）qsが与えられたとき，入力系列Jによる順序 機械の状態遷移は，M（S（o），J）と表わされる．この 値は当然Sの部分集合となる．SJ＝M（S（o）， J）とす るとき，このSJに含まれる状態の数が少いほど，入 力系列Jによる状態遷移に関する情報のあいまいさが 小さくなることは明らかである．
いま，1（＊）なる入力系列が存在して M（S（o），1（＊））＝s（＊）ε5
なるs（＊）が唯一つ存在するとすれば，1（＊）による状 態遷移はS（o）におけるすべての状態に対して，あい まいさのない情報をもつことになる． このことは，
S（o）に含まれる任意の状態が，入力系列1（＊）によ り常に定められた状態s（＊）に遷移することを表わし ている．
ここで，1（＊）によるS（o）の状態遷移過程を考え てみる．1（＊）よりも短い系列Lr（＊）が存在して，
M（S（o），1−r（＊））＝s＊＆M（s＊，Ir）＝s（＊）
（ここに，1−r（＊）・1・＝1（＊）である．）
となる場合，1一，（＊）と1（＊）は次の定義により本質的 に区別される．
（定義3・1） 状態集合S（o）に関する同調系列 を次のように定義する．なおIAIは， Aが集合のと きは元の数を，系列のときは長さを表わすものとする．
人力系列Jと， Jよりも長さが一つ短い系列J−1に
対して，
IM（S（o），J）1＝1＆IM（S（o），J−1）1≧2 となるとき，JをS（o）に関する同調系列といい，こ のようなJを1＊と表わす．また，
M（S（o），1＊）＝s＊
なるs＊を同調状態という．これに対して，
ヨ1．，M（s＊，1，）ニs（＊）
なるS（＊）を準同調状態，1＊・1，ニ1（＊）を準同調系列 という．
次の定理の成立は明らかである．
〔定理3・1〕 部分集合S（o）に対して，
ヨ1（＊），M（S（o），1（＊））＝s（＊）
であるとき，
ヨ1＊，IM（S（o），1＊）1＝1＆II＊i≦II（＊）1 が成立する．
部分集合S（o）に関する部分同調性の定義を次のよ うに与える．
（定i義3・2） 部分集合S（o）dSに関して（準）
同調系列が存在するときおよびそのときに限り，機械
はS（o）に関して部分（準）同調するという．
清 木 泰 弍 定義2・2に1（＊）を適用すれば，
VSi（o）q S， M（Si（o），1（＊））＝M（S，1（＊））
となるから，部分同調性により完全同調性の定義が次 のように与えられる．
（定義3・3） 5における任意の部分集合S（o）
に関して，機械がs（勤に部分準同調する場合および その場合に限り，機械はs（＊）に完全準同調するとい
う．
また，M（S，1＊）＝s＊なる1＊が存在して，
IM（S，1−1＊）1≧2
なるときおよびそのときに限り，機械はs（＊）に完 全同調するという．
次に機械が任意の部分集合s（o）から同調状態にい たるまでの過程を，状態集合の元の数の変化について 考察し，機械が同調系列をもつための必要条件として，
M（Si， x）＝M（Sj，x）sI≒Sj（P）
なる状態対（Si， S」）が存在することを示す．いま，
Ii＝XIX2……XiなるIiに対して iM（S（o）， Ii）1＝mi
とすれば，任意のiに対してmi≦lS（o）1調mであ ることは明らかである．
同調系列1＊＝XlX2……Xwが存在する場合， この
miの値はm1（≦m）からmw＝1に減少していく
から，状態遷移過程において少くとも二つの異なる状 態が，同じ入力により同一の状態に遷移するはずであ る．もし，そのような状態遷移が存在しないと仮定す れば，S（o）におけるm個の状態はすべての入力に対し てm個の異なる状態に遷移するから，miの値は常に mとなる．したがって，miの値がmよりも小さく なるためには，（P）式を満たすような状態対が少くと も一つ存在しなければならない．
このような状態対が一つ存在するとき，同調系列が 存在することを以下に示す．
M（Su， Xw）＝M（Sv， Xw）＝s＊
とすれば，次のような状態遷移が可能である．
，1・・sl・・…・・瑠・一町、壬・・、1……・瑠・三……
三㌧、壬・）……鋤一飾・・一、岳・）主
，・・
蛛E・…・・瀞…・瑠・竺………よ
・1「）、彦「）一……一一蕪一一・＊．
ゆえに，同調系列1＊＝XIX2……Xw……X。……Xwが
存在する．
以上の事から，次の定理が成立する．
〔定理3・2〕 機械が同調系列をもつための必要
条件は，M（s。， x）＝M（s。， x）なる状態対（s。， s。）
が少くとも一つ存在することである．
S・，S。が同じ入力によりともにS＊に遷移し，かつ S＊が同調状態となるとき，（S・，S・）を同調状態対と いう．このとき，定理3・2は次のように表わすこと
もできる．
〔定理3・3〕 機械が同調系列をもつとき，
Vxε．Σ， M（si， x）＝M（sj， x）i≒jなるすべ ての状態対｛（Si， Sj）｝の中には，少くとも一・つの同 調状態対が存在する．
次に同調系列をもつ機械と，その状態遷移表から同 調系列を求める方法の一例を示す1）．Fig．1のよう に与えられた状態遷移表から，Fig．2に示すような 同調グラフ1）が得られる．この図から，（2）と（5）が 同調状態となることがわかる．（2）に対する同調系列 として，000，1000，llOOO等があげられる．（5）に 対する同調系列も，図から容易に求められる．なお，
この機械のすべての状態が準同調状態になりうること も明らかである．
0 1
1
2
3
4
5 2
2
1
3
3
3
4
5
5
3
0
Fig．1． State transition table．
（12345）
（123） 一一
（345）
。／：L。の／・＼
＼／・
一←一一一 i35）
一一
P②＼岡＼
1し）
1
0 （4） 1》（5）
Fig．2． Synchronizing graph．
4，SP分割をもつ機械の完全同調性
順序機械の動きをその内部状態の種々の分割により 表わす研究は，主にHartmanis2）によって行われ，
代数的に体系づけられた論文もいくつか発表されてい る．ここでは，状態分割の中でも，特にその状態遷移 に関する閉包性によって特徴づけられているSP分割 をもつ機械について，その完全同調性を，状態ブロッ クに対する完全同調性および状態ブロックに関する部 分同調性の二つの側面から考察してみる．
定義2・5により，SP分割をもつ機械の状態ブロ ックに関する動きは，そのimage machineの動き と一対一の対応をしているから，機械の完全同調性に 関して次の定理が得られる．
〔定理4・ユ〕 唯一つのSP分割πをもつ機械
・4が完全同調するための必要条件は，オπが完全同調 することである．
（証明） オがs＊εBπ（s＊）に完全同調するとき，
すべての状態ブロックに対して
ヨ1＊，VB冗（o）， M（Bπ（o），1＊）＝s＊εBπ（s＊）
となる．ここに，Bπ（s＊）はs＊を含む状態ブロック を表わす．このときAπは，
VBπ（o），M7（Bπ（o），1＊）＝Bπ（s＊）
となるから，定理3・1によりオπが完全同調するこ とは明らかである． （Q．E．D．）
〔定理4・2〕 唯一つのSP分割πをもつ機械
オにおいて，
ヨJ＊，VS（o）qS， M（S（o♪， J＊）．dBπ＊
が成立するための必要十分条件は，・4πがBπ＊に完 全同調することである．
（証明） aBπ， S（o）⇔BπなるS（o）に対しては，
M（S（o），J＊）qM（B売， J＊）⊂IBπ＊
となるから，このとぎ・奪に関して Mπ〈S（o），J＊）＝Mπ（Bπ， J＊）＝Bπ＊
となり，任意のS（o）およびB・に対して定理の必要 条件および十分条件がともに満たされていることがわ
かる．
S（o）dBπでないS（o）に対しては，
S（o）d｛Si（o）iSi（o）εBπ（i）；i＝1，…， m｝
とするとき，
M（S（o），J＊）（＝M（Bπ（1）Bπ（2）……B乳（m）， J＊）
qB7＊
となるから，・娠に関して
Mπ（S（o），J＊）＝Mπ（B冗（1）Bπ（2）……B冗（m），J＊）
＝Bπ＊
が成立する．したがって，この場合も定理の必要条件
および十分条件がともに満たされていることがわかる．
（Q，E．D．）
二つのSP分割π，τが存在してπ≧τとなるとき，
機械の完全同調生に関して次の定理が得られる．
〔定理4・3〕 π≧τなる二つのSP分割π，τを もつ機械浸において，岳がBτ＊に完全同調するた めの必要十分条件は，・張が完全同調し，かつその同 調状態ブロックに関してオτがBτ＊に部分同調する
ことである．
（証明） ・4τがBτ＊に完全同調するとき，任意の Bア（0）：およびBπ（o）に対して
ヨ1＊，Mτ（Bτ（o），1＊）傭Mτ（Bπ（o），1＊）
＝Mτ（｛BT（o）｝，1＊）＝Bτ＊
となる．τ≦πであるから，Bτ＊dBπ（＊）なるBπ（＊）
が唯一つ存在する．したがって・4πに関して，
VB冗（o），Mπ（Bπ（o），1＊）＝Bて（＊）
となるから，定理3・1によりオπが同調状態ブロッ クBπ＊に完全同調することは明らかである．また，
Bπ＊＝｛BT（o）｝であるから， このBπ＊に関して缶 がBτ＊に部分同調することも明らかである．以上で，
定理の必要条件が証明された．定理4・2と B冗＊に 関する盃の部分同調性とにより，定理の十分条件が 証明される． （Q．E．D．）
定理4・2と定理4・3において τ＝｛61，§2，…，
s・一1，§・｝とすることにより，次の系が得られる．
〔系4・3・1〕 SP分割πをもつ機械オがs＊
に完全同調するための必要十分条件は，・4πが完全同 調し，かつその同調状態ブロックに関して・4がs＊
に部分同調することである．
0 1
1 2 3 4 5 6 7 8
5 6
6 5
7 6
8 5
1 7
2 8
3 5
4 6
Fig，3． State transition table．
以上の定理を応用して，Fig．3のように与えられた 機械の同調系列を求めてみよう．
冗＝＝U234；5678｝＝＝ ｛Bπ（1），B冗（2）｝，
清 木 泰 弍
τ ＝｛12 ； 34 ； 56 ； 78｝
ニ・｛Bτ（1），Bτ（2），BT（3），Bτ（4）｝
とする．まず，オπは同調系列1によりBπ（2）に完 全同調することがわかる．このB冗（2）に関して，オτ は系列OlによりBT（3）に部分同調する．さらにこ のBτ（3）に関して，オは系列10により状態（3）
に部分同調する． したがって，機械オは同調系列 10110により状態（3）に完全同調することがわかる．
次に，π・τ＝0なる二つのSP分割π，τをもつ 機械Aが完全同調するための条件を求めてみる．機械 が完全同調すると仮定すれば，SP分割の状態遷移に 関する閉包性により，冗およびτの各々の分割に対 してそれぞれ独自の同調系列が存在するはずである．
したがって，次の二つの式が同時に成立する．
ヨ1＊，VBπ（o），M（Bπ（o），1＊）＝u＊ （1）
ヨJ＊，VB7（o）， M（B7（o）， J＊）＝v＊ （2）
ただし，u＊キv＊，1＊≠J＊とする．
系4・3・1より，（1）式から次の（3）（4）式 が得られる．
ヨ11＊，12＊，VBπ（o）， Mπ（Bπ（o），11＊）＝B7＊
（3）
＆M（B冗＊，12＊）＝u＊ （4）
ここに，11＊・12＊＝1＊ である．
同時に，（2）式から次の（5）（6）式が得られる．
田1＊，J2＊， VBT（o），Mτ（Bτ（o），J1＊）＝Bτ＊
（5）
＆M（B」＊，J2＊）＝v＊ （6）
ここに，J1＊・J2＊』J＊ である．
（3）式は分割πに関する状態遷移を表わしているが，
定理4・2により分割τにおける任意のBτ（i）に対 しても成立するはずである．したがって，Bτ（i）に対
して，
M（Bτ（i），11＊）dBτノ，＆B71口B冗＊
なるB7ノが唯一つ存在する．ところが，冗・τ＝0で あるからBτノdBπ＊を満たすようなBτノは，唯一つ の状態からなる集合でしかもB7＊に含まれるもので なければならない．したがって，あるBτ（i）に対し て
M（B7（i），11＊）＝Si＆SiεBπ＊ （7）
なるSiが唯一つ定まる．（7）式が（5）式を満たす ことは明らかである．同様にして，任意のBπ（」）に 関して次の（8）式が得られる．
M（Bπ（」），J1＊）＝Sl＆SjεBT＊ （8）
（8）（7）式が成立すれば，（4）（6）式において，
12＊＝J1＊およびJ2＊＝11＊とすることにより， B冗＊お
．よびBτ＊に関する部分同調が可能である．したがっ
て，（1）および（2）がともに成立するための必要十 分条件は，（7）および（8）がともに成立すること
である．
以上のことから，次の定理が得られる．
〔定理4・4〕 π・τ＝Oなる二つのSP分割π，
τをもつ機械が完全同調するときおよびそのときに限 り，次の二つの入力X1， X2が同時に存在する．ただ し，X1≒X2．
VBτ（i），M（Bナ（i）， x1）＝SiεB究＊ （9）
＆∀Bπ（」），M）Bπ（」），x2）＝SjεB7＊ （IO）
Fig．4において，π・τ＝0なる二つのSP分割π，
τをもつ機械の例を示す．機械Aは，入力1が（10）
式を満たさないので，完全同調しない．また機械Bは，
入力1が（9）式を満たさないので，完全同調しない．
機械Cは，入力Oが（9）式を満たしかつ入力1が
（10）式を満たすので，系列Olにより状態2に，また 系列10により状態1に完全同調することがわかる．
0 1 0 1 0 1
1
2
3
4 2
1
1
2 4
3
2
1 2
2
3
3 4
3
2
1 2
1
1
2 2
2
3
3
（A） （B） （C）
Fig．4． State transition table．
5．同調系列をもつ機械の誤り訂正能力
機械内に生じる誤りとして，状態誤りがあげられる．
疹，S1となるべき状態が誤ってS2になったとき，
（S1， S2）を状態誤りといい，（S1， S2）εEと表わす，
ここに，Eはすべての状態誤りの集合を表わし， Ed S×Sである． この状態誤りが一時的なものであり，
いっかは訂正されうることを次のように定義する．
（定義5・1）3） 次の式が成立する場合およびそ の場合に限り，一時的な状態誤り（S1， S2）は訂正さ れるという．
ヨIV（s1， s2）εE， VJ， M（s1， JI）
＝M（s2， JI）
（1）式を変形して次の（2）式を得る．
M（M（s1， J），1）＝M（M（s2， J），1）
ここで，
M（s1， J）＝si， M（s2， J）＝sj とすれば，（1）式は次のように表わされる．
（1）
（2）
Vsi， sj， M（si，1）＝M（sj，1） （3）
（3）式が成立するための必要十分条件は，与えられた 機械に同調系列1＊が存在しかつ1＝1＊となることで ある．また，この1＊により（3）式が成立するのは，
そのとき機械が状態誤りを含まない正常な状態である 場合およびその場合に限ることは明らかである．した がって，状態誤りを同調系列により訂正する場合，状 態誤りの存在範囲を同調系列の適用範囲外に限定する 必要がある．
（定義5・2） 状態誤り（s1， s2）が長さkの入 力系列により消滅する場合およびその場合に限り，
（S1， S2） ε E（k）
と表わす．
この定義と上記の考察とにより，次の定理が得られ
る．
〔定理5・1〕 完全同調する機械において状態誤
りが生じたとき，
3：1＊，V（s1， s2）， VJ （「Jl＝＝k），
M（s1， JI＊）＝M（s2， JI＊）
すなわち，状態誤りを訂正する同調系列が存在するの
は，
