言語機械代数（第3報）
Σ＊一右線形方程式II
（昭和56年5月30日 原稿受付）
情報工学教室安在弘幸
九大理学部南 俊朗
情報工学教室重松保弘
Language Machine Algebra（Part 3）
Σ＊−Right Linear Equation II
by Hiroyuki ANZAI
Toshiro MINAMI Yasuhiro SHIGEMATSU
Ab8tract
In this paper， the 3 rd report of Language Machine Algebra or Semi・linear Algebra， it is shown that
the theorems given in the 2nd report introduce such various methods to solve theΣ＊・right linearequation that are analogous to and generalized from the various methods to solve simultaneous linear eqUatiOnS in nUmeriCal analySiS．
The problems solved in this paper are interpreted as the problems to obtain languages accepted by
given finite automata and furthermore as the several problems concemed with graph theory shown inthe 2 nd report・
この算法がΣL行列に適用される場合として，Warshal1 7．最小解の計算 の定理7）として有名な推移閉包算法が導かれる。
7．4節では，数値解析におけるEscalator算法に準じ この章では，与えられたΣL右線形方程式： た算法としてCarr66）などが示した一般化Escalator算法 x＝Ax＋￠ （7．1） が基本定理より得られることを示す。
の最小解・4㌔を具体的に求める方法を示す。 7．1 消去法（1）
7．1節では，方程式の右辺から遂次的に変数を消去し
てゆく消去法を示し，7．2節では，これを組織的に行な Σ＊一右線形方程式：
う；．㌶二去當▲巖1》に， 運㌻（7 7）｝（7・2）
㌶鷲巖灘蕊議㌶：い右辺から拘の項を消去したい・部分閉包化定理4・2よ
算法を示す．これは，数値解析醐ナる掃出し法に相当り・κ・は次式で表わされる・
し，dondran5）が一般化Gauss−Jordan法と名付けた方 κゴ＝莇（Σα」〃κ々＋C」白幸」）
法である。なお，この方法は，McNaughton・Yamada4） 従って，これを式（7．2）の右辺に代入すればよい。こう
が有限オートマトンの状態遷移図から正規表現を求める して，式（7．2）の右辺からすべての変数項を消去してゆ
ために与えた方法の行列計算表示になっている。そして・ けば，最後に定数項として，最小解が得られる。
〔例7．1〕 次の右線形方程式の最小解の第1成分κ1を とおき，同様にしてκ。−1の項を消去する。
求める。 こうして，κ・−2の項，κ。−3の項，＿，κ1の項と遂次消 κ1 0＋b α b κ、 α6 去してゆけば，最後にκ1の解が定数項に得られる。
x、＝φ α＋が α、が κ、＋b このとき得られた方程式の形は，次のようになる。
（解）
匡］［賦φ鷲］［φ］
κ3ニ（bα）率κ1＋（α＋6）κ3 ＝（α十b）＊（●∂牢κ1
κI
X2
κn
φ……・…・・φ κ1 α21 ・． 三 κ2
α。・…α。㌃．1
ﾓガ。
十
β、
β2
β。
（7．5）
＝（α十6）・κ1 〔注記〕 方程式（7．2）を有限オートマトン4の状態特性
。、ニ（o十が）。，＋〆b・。、＋6 方程式（または右線形文脈舳文法GのBNF）とした
とき，」4の受理言語（またはGの導出言語）が式（7．5）
＝（α十が）＊（♂がx3十b）
＝（α十b）W。、＋6） の定数項ベクトルの第1成分β1として得られたことにな る。
＝（o十b）＊（x3十b）
もし，最小解ベクトルのすべての成分を求めることが
＝（α十6）＊（（α十b）＊κ1十b）
ニ（α十b）・（。1＋b） 必要であれば・式（7・5）｝こ対し・系6・1・1を再び用・・るこ とによって，次のように求めることができる。
これらの式を使ってκ1を求めると，
κ、＝（α十δ）κ、＋ακ2＋b為＋αb 第2段階 系6．1．1において，
＝（α十b）κ1十α（α十δ）率（κ1十b）十b（0十●）＊κ1十αb エ1ニ（κ1）
＝（α十b十α（α十b）寧＋b（・＋6）・）。1＋。（。＋●）・b＋。b X・＝ ぽ・，・・，＿，・・）
＝（o十b）（α→−6）＊x1＋o（α＋b）％ とおくと，式（7．5）は次のようになる。
＝（（α十b）（α十b）つ＊α（α十6）＊b
＝（o十b）＊α（α十b）＊b
κ1
κ2
7．2 消去法（2） κ3
前節7．1で述べた方法は系6．1．1を用いることによって
Gaussの消去法に準じた組織的な方法に組立てることが できる。これを次に不す。
xπ
φφ …………φ φφ …………φ
＝ φ α32 ・・． i
φα。2…θ。。．1φ
κ1 β1
κ2 α21β1＋β2
κ3十 i
κ刀 αn1β1＋β刀
（7．6）
＿ 次に
工1＝ぽ2）
第1段階 系6．1．1の式（6．10）において， x2＝z（κ3，＿，κ・）
κ1＝ （κ1，κ2，＿，κ。．1） とおき，式（6．11 ）によりκ2の項を消去し，同様にして，
x2ニ（κ。） κ3の項，＿，κ。，1の項を消去してゆくと，定数項として
とおく。すると，式（6．11）によって，式（6．10）と最小解 目的の最小解が得られる。が等しい方程式が次のように得猟ちの項が消去され 〔肌2〕次の右線形方程式の最小解を求める．鵬）
る。
：：㌶鷲一酬；：1： ［ii］−1∴正川．
次に・式（7・3）において・ 第1段階次のように41、，412，∠21，422を定める。
・ ㍍ll∴ 扁 ム＝｛三二δ｝，血＝口，
（脚注）見易さのためφを一と記すこともある。
421＝〔一一〕，∠22＝〔一〕 互蓮 すると，式（7．3）および式（7．4）はそれぞれ次のように （i） ・←A
（ii）々＝1，2，＿，ηについて次を計算する。
なる。
…（｛こごb｜＋自〔φ 〕←寸週＋日〔ず〕ご 一＋じ1］嚥』㌦）
・＝
kこ顯泊＋〔λ笥一〔惣〕勘＋｛：｜ ここで仇喘）（1≦ち∫≦。）κ3＝〔φ・〕〔一ゴェ1＋〔φ・〕〔α・〕ニα・ ・＋1＝A＋
これを右線形方程式として表わすと，次のようになる。 （証明）零列化定理6．1より，次が成り立つ。
［1］一ピユii］＋［i］ X−［窯：：：］X＋［：］（7・8）
＝L］［ii］＋｛割 ：繕識i蕊警！叉：ご
さらに・ 同様にして一般に次が成り立つ。
［ii］ニL三正i謄㌻］ x−［i篇：H《］㎝）
7．3＿般化掃出し法（一般化G・脚J・・dan法） これは式（7・7）｝・おし〉て 一々の場合に相当する・なお・
式（7．7）においては，式（7．11）におけるψ＝1，2，＿，ηの 与えられたΣ＊一右線形方程式に対して・その係数行列 各々の場合が同時的に計算されている。
のすべての列に零列化定理6・1を適用すると・定数項に 従って，〃；1，2，＿，ηについて，式（7．9）より始めて，
最小解が得られる。これを組織化した方法を次に示す。 式（7．11）を再帰的に用いて計算してゆくと，最後の式の
〔定理7．1〕（零係数行列化定理） 係数行列はφになる・すなわち次が成り立つ・
黶Fil］イilト＝・［li：：縢］
入力 ％×ηΣ＊一行列A
百万Aの正胞行列A・ ゆえにA＋＝A＊仁 蝋 （証明終）
式（7．12）において， または∫がゐに等しいとき，そ れぞれ次が成り立つ。
（a）ノニ〃のとき，∀ εガについて，
沈〜髪＋1）＝〃21儂）＋彬1；）〃2〜鍵＊〃21三）
＝φ＋沈繍・λ （7・13）
十
〃21々
η2触
〃2πA
〔〃2麦為〕〔〃2姐…〃2力，々−1λ〃2向，舟＋1…〃2々π〕
τ
（7．7 ）
（b） ＝カのとき，∀ ε百について， 一方，ノ1の閉包、4＊を計算する場合には，式（7．15）お 城膓＋1｝＝初1θ＋ 2纏〃21㍗〃2〜2 よび（7．16）にλを加算すればよいことになる。従って（c）
一φ＋欄瑠 （7・14） は次のよう1・なる。
（C） ＝∫＝〃のとき， （C ） 21叢＋1）ニ 2〜駕十 21ξ〜 2偶㍉η盟十λ
繊1・＝噸＋熾豊・蛾 ＝φ品豊＊λ （7・17）
＝φ＋峨＊噸 （7・15） ゆえに，式（7．13），（7．14）および（7．17）より次が得ら
＝φ＋繊噸＊λ （7・16） れる。
こうして，式（7．14）と（7．15）より，式（7．7）における冗
長な項を除去して改良した算法欲のように得られる。 〔鵬閉包難〕
〃×ηΣ＊一行列Aに対して，11の閉包、宇は次の算法
川 吐 によって求めることができる。
（ii）々＝1，2，．．．，ηについて次を再帰的に計算する。
入力 η×ηΣ 一行列A 遅 ． 出力 Aの閉包行列、4＊
211 21η
〃2η1 ．〃2πη
十
←
〃2肋
〃2鹿＿1虎 λ
〃2向＋1身
〃2肋
〃211 〃21舟 ° 〃21η
2鹿一11 2々−1ピ 2白＋1η
φ … φ … φ （々
〃2占＋11 °〃2力＋1身 〃2々＋1η
〃2nl 〃2π向 〃2nn
〔 ＊カ2舳〕〔物尭1…〃2肋 ・・〃2肋〕
（ （
遊（i）〃←A
（ii）
〃211 〃21η
2A1 ° 〃2白n
〃2η1 〃zηη
←
初11…φ…卿1n
φ …φ…φ
吻川…φ…〃2πη γ α ん （
（カ （7．7 ）
十
〃21々
λ
〃Z励
（〃
〔 ＊ 2々A〕〔〃2丘1…λ…〃2々。〕
τ
（〃 （7．18）
同様に・式（7・13）と（7・
ﾟ・式（7・7）における冗長 AがΣ・一行列であるとき，式（7．7りの一‡、は必ら な項を除去した式が次のよ・にも得られる・ ずλになる．従って，この項を式から除去することカ、で〃211 〃21η
〃2η1 〃2ππ
卿11…初1，為＿1φ物1，力＋1…吻1η
← 初々1…沈々，々＿1φ初盈，々＋1…沈Aπ
沈π1…勿π，此＿1φ沈η，々＋1…卿朋
きる。こうして次の系が得られる。この系は，Warsha11
のプール行列の定理7）として有名な推移閉包算法（transitiveclosure algorithm）である。
なお，高岡・福地は，この算法も含めて幾つかの算法
を検討している：）
〔系7．1．1〕 （推移閉包算法） がδ が♂ がo だ♂〔（α＋b）＊〕〔＿α＋b＿〕
η×ηΣ゜一行列Lに対して，Lの正閉包L＋（推移閉包 〃＝ 一 一 ＿ ＋ λ
と呼ばれる）は，次の算法によって求めることができる。 ＿ ＿ ＿ ＿入力 η×ηΣ゜一行列L が6 が♂＋ゲ♂（α十b）＊（α＋の ゲα 出力 η×ηΣし行列L＋＝〃。＋1 ＝ 一 （α十b）＊（α＋b） 一
方法 一 一 一
（i） 〃1←L がb が♂（α十b）＊ がα
（ii）』1，2，．．．，ヵにっいて次を計算する。 ＝ ＿ （糾b）・（α＋6）＿
〃此＋1←〃々十 初IT
沈1㍑
初〜8
ここで〃・＝（勿〜1））（1＜ ＜η，k∫＜η） がbがc・（。＋b）・がα
［］［］
［ ］
峰＿〕 ［一一一］
β 々＝3の場合，
（α （7．19）
弔㌘㍑）Tr〕〔一一一〕
（算法終）＝［ニー…）：］
一般に式（7・19）において・次が成り立つ。 この行列がAの正閉包、4・である。
〃2〜〉＋1｝＝卿〜○｝十〃2〜乞）〃2〜6） （7．20）
7．4 一般化Escalator法 上式において，i＝々または∫＝〃のときそれぞれ次が
成り立つ。 数値解析におけるEscalator算法に準じた算法として・
隠：ll：：：2灘き ；蕊㌫㍗た算法を次蹴そ
従って式（7．19）において（α）項，（β）項の祝〜Xはそれぞ 〔補題7・1〕行と列がそれぞれ〃2とηに分割された2つ
れφであってもよい。 の行列：
〔肌3〕次の行列Aの正閉包腔求める． A＝［鴛：〕およびβ＝〔竪：：〕
弍ヨ lllこ1㌘ご；…一
（川〃＝A
B22＝（AL 22十∠421／1㍍ノ112）． （7．22）
（ii）まず・ ＝1の場合・ β12ニAf1A12B，， （7．23）
一［ヨ＋［λ］〔が〕‥ 翻1：：：篇㌫ ：；： ；
…∴ヨ 子｛㍊1；：：に
一x＝ k三1ゴ（〔＝：：lx＋E） A篭㌶驚禦＝（砺）に対して 次の算法は 一［竺；｜（〔晶1：｜x＋E） ㌶蒜言景＝（晦）
七笥x＋〔勾 方法
一x−
o訂（〔二笥牢；｜）L［1㌫Hill：：：il］
一瓢：笥牢；〕）：：㌫〔㍍＿て計算する．
今二三鷲1驚曇吻イ…副｛il∵：：：i：］じ］1
る二訂（｛：竺寧＋し瓢；〕） じ］］li∵：：∴］隠園
一〔三三〕（［：当肝ぱ㍍；〕） ㎞…一←㎞〕㎞…姻［∵i∴］
▲∴：！1鶯1▲ （ll：IJ㍑：lilJ
［三笥｛1亮｜ （証明）
＝㍗轡品慧
細＝ｶ∵il∴ト｛烈
ゆえに，次が成り立つ。 、421＝〔〃2為1＿〃輪一1〕， 、422＝〔〃隔〕
β22＝α；2＝（ん2＋ん1A㍍小2）＊
B12＝、4f1、412β22 とおくと，補題7．1より3．が成り立つ。 （証明終）
B21＝α21＝β22A21Af1 〔例7．4〕次の行列Aの閉包A・を求める。
．811＝、4f1＋、4f1、412B21 （証明終）
咋≡］ 1：∴るA 徽
3・ 本稿で示したΣ・＿右線形方程式の解法については，
々＝2暢合 オートマトン輪側からよりもむしろ，グラフ理論側か
〔勿22〕＝（〔叶b〕＋〔一〕〔が〕〔cつ）＊ らの寄与が多い。これは，この方程式が，その解釈を適
＝〔（α＋6）つ 当に行うことによって，グラフ理論の多くの問題の定式
〔微2〕＝〔が〕〔Cつ〔（α＋b）つ 化になることから，それらの問題について既に得られた ＝〔b＊c＊（α十b）り 解法が一般化されたからであろう。〔 221〕＝〔（α＋b）つ〔一〕〔が〕 ところで，数値解析における解法に類似の種々の解法
二〔一〕 が，両者の側から，それぞれ独立に得られたのは興味深
〔〃211〕＝〔b＊〕＋〔が〕〔がc＊（α＋6）＊〕〔一〕 い。例えば，McNaughton・Yamada・）は与えられた有 ＝〔ゲ〕 限オートマトンからその受理言語を得る算法を与えたしたがって，ルfは次のようになる。 が，この方法は本稿において零係数行列化定理で与えた
〃＝［ゲがc＊（α＋●）＊iα一 （α十b）＊ i一］ 嶽鶯㌘鷲諭；；三㌶
さて，有限オートマトンと名札付有向グラフとは盾の
＝3の場合 両面的存在であり，従ってそれらを扱う有限オートマト
〔〃233〕＝
i〔一〕＋〔一一〕ヒゲ嵩ダ〕ヒ｜｝ 嶽：1隠翼瓢警鶏：欝：㌶ε＝〔λ〕 ている。
｛：：］＝［；㍑門日〔λ〕 参考文献
一閂 1）ゴ㍑㌔二㌶纂欝竺；；霊熟頴㍑
一〕＝〔λ〕〕P㍗笥 ・；i無謙慧綴誌よ；1九工
＝〔＿＿〕 3）安在，南，重松： 言語機械代数（第2報）ΣL右線形方程式1 ，
ピ〕；｛ニゲ瓢 ・li繍鷲羅麗竃ご鷹
＋｛：鷺網〔一一〕・i驚き蕊＝：蒜漂聯B
6）Carr6， B．：t℃raphs and Networks， Clarendon Press・
Oxford，1979．
7）Warshall・S・：t¶A theorem on Boolean matrices， J．
ACM 9，1， pp．11−12（1962）．
