九州工業大学学術機関リポジトリ Title Author(s) Issue Date URL 言語機械代数(第4報) : Σ＊‐右線形方程式III 安在, 弘幸; 南, 俊朗; 重松, 保弘 1981-09-01T00:00:00Z http://hdl.handle.net/10228/4248 Rights Kyushu Institute of Technology Academic Repository 九州工業大学研究報告（工学）No．43 1981年9月 ． 123 言語機械代数（第4報） 、Σ㌧右線形方程式m （昭和5｛ミ年§i月3◎日 原稿受イ寸） 情報工学科安在弘幸 九大理学部南 俊朗 情報エ学科重松保弘 Language Machine Algebra（Part 4） Σ＊−Right Linear Equati◎n皿 by Hir◎yuki ANZAI Toshiro MINAMI Yasuhiro SHIGEMATSU Ab8tra￠t F◎rag輌ven regul訂express輌領there輌§the pτ◎blem秘c◎nstmct a finite砿omat◇n oτa right linear context−free grammar which accepts or derives a languagごrepresented by the regular expτe§sion． Becau§e aΣ一right lineaτeqatl◇n輌§i就αpreted as a state chaτacter輌stic equation of the automaton or as a Backus Naur Form of the grammar， this comes to the problem t◎◎btai鯖heΣヰighパineaτeqUa乞iOn of Wh輌ch the SdUti◎n輌S eqUal to a Set repτeSented by the regular expression． Th輌§pap啓ぱesents va蓄iou§alg◎品hm§to solマe the pmblem◇n basis◎f the theorems g輌ven in the previous report 2． 式論において，与えられた幾つかの正規表現に対して， 8．Σ一正規表現のΣ一右線形方程式特性化 それらの間の等価，包含，交差または素なる関係を一挙 正規表現が与えられたとき，それを受理言語（導出言 に判定する算法を与える際に利用することを考慮してい 語）とする有限オートマトン（右線形文脈自由文法）を るからである。 構成する問題がある。有限オートマトン（右線形文脈自由 与えられた（幾つかの）正規表現に対して，それを解 文法）の状態特性方程式（BNF）はΣ一右線形方法程式 （ベクトルの成分）に持つようなΣ一右線形方程式を求 と等価であるから，この問題は，その正規表現（に等価 める算法（8と呼ぶ）を2通り与える。第一の算法は下降 な正規集合）を解ベクトルの成分の1つ（通常は第1成 型（toP−down type）で筆算向きであり，8．1節で与え， 分）に持つようなΣ一右線形方程式を求める問題に帰着 第二の算法は上昇型（bottom−up type）で機械（計算機） できる。このことを、Σ一正規表現のΣ一右線形方程式特 向きであり，8．2節で与える。 性化という。この章では，この問題を，r個のΣ一正規 下降型の算法は，零列化定理6．2と空語自由化定理5．1 表現が与えられたとき，これらを解ベクトルのどれかの より導かれる。この算法では，与えられた正規表現が1 成分として持つような，Σ一右線形方程式を求める問題 個の場合，得られたΣ一右線形方程式の次元数（有限 として一般化し，それを機械的に解く算法を与える。そ オートマトンの状態数）は，その正規表現の連接と閉包 の理由は，1つには非初期オートマトンへの一般化を考 の演算の回数に2を加えた数を越えることはない。 慮していることであり，いま1つはm部Σ一右線形方程 一方，上昇型の方法では，まず非決定性有限オートマ 124 トンの和，連接および閉包等の合成定理8．1を，部分閉包 化定理4．2および零列化定理6．1より導き，これを基に正 規表現の再帰的定義に沿った構成法を与える。 △11＝ 8．1 下降型の変換法 ノ ノ ノ α11°”6ZIJ°”6Z1η ノ α‘1’”α‘」’”α‘η α1 △12＝ αゴ （85） ノ ノ αη1’”αηゴ’”απη αη 与えられたΣ一正規表現R1，是，…，R，｝、対して，右 △21＝［β1’”鳥’”β・】 △22ニ［γ］ 線形方程式： ここで 侮￡＝〆烏、＋α彪ゾβ （8．6） x＝・4x＋e （8・1） （なお，△11の第（‘，∫）要素以外の要素乏z（（〃，1）キ は，次の条件： （ちノ））の最も簡単な定め方は，〆κ＝0白、かつ 偽＝β＝ 10∀γεあヨCε死：R・＝εご・A㌔ φ とすることである。） 20 ∀‘ε蕗：［￠］」εP（Σo） （8．2） 3°∀‘，ノεガ：［∠4LεP（Σ） ［3］可能な限り［2］を繰り返す。最終的には，係数 を満足するとき・R1・R2・…・R・を特性化するという。 行列のどの要素もP（Σ∪Σ・）に属するようになる。 （例） 特；瓢型1’一組の正規表現のΣ一右線形方程式 ぱ）＋、一㍗1 入力Σ一正規表現R1，島，…，R， φ 叶励＋bi・ 出力条件（8．2）の1・，2・および3・を縦する右線形方 →…4……………ζi；．．………i．．f一 程式 6＋6 φ iφ こうして得られた右線形方程式は，条件1°，2°および ［2］ η元の右線形方程式x；・4x＋cが条件1・，2・を 3°を満たす。なお，上記の変換過程の途中で適宜補題6．2＼ ＼、 満足するとき，次のκ＋1元の右線形方程式： を用いて方程式の元数（‘．ε．行数）を減らすことができる。 ［乳＋ぽ1［㌫］＋［；1（84）こ麟ま欝跳鏡覧蕊㌫， 得られるΣ一右線形方程式の解ベクトルの第1成分が， が条件1°，2°を満足するには， このΣ一正規表現に等しくなる。 ∠4＝△11十△12△膓2△21 が成り立てば十分である。（系6．1．1） ［算法8．2］6：Σ一正規表現のΣ一右線形方程式特性 そこで・・4の少なくとも1つの要素砺に項αゼγ＊β、（キ 化（下降型，筆算向き） φ，ただしγ＊＝λのときα峠λかつβ」キλ）が存在する とき△11，△12，△22および△21を次のように定める。 入力 、Σ一正規表現 R 出力 Rを解（ベクトルの第1成分）とするΣ一右線形 方程式 方法 1∼に次の規則を可能な限り適用する。この規則 125 において，αおよびβはΣ一正規表現を表わす。規則の 物全0κ1として 適用のある段階における変数を，為，κ1，…，κmとする。 x1＝1物＋0傘01κ1＋0＊陥 4° このとき，κとyは既に導入されている変数κゼ（0≦ 為全1苅として i≦初），zは新しく導入される変数Xm＋1を表わすものと x1ニ1物＋0＊0為＋0％ 4° する。また，新しく変数zを導入し，そのzの定義式を 石合0為＋0石として z＝〈式〉とすることを9全〈式〉と表わし，定義式κ＝ 苅＝1物＋0為＋0石＋0奉祝 6° 〈式1＞を定義しなおしてx・＝〈式2＞とすることをκ＝ 為全0為＋痴として 〈式1＞→∫＝〈式2＞と表わす。定義式の右辺で，先 苅＝1物＋0為＋0石＋0為＋為 6° 頭の・…＋・や後続のe＋…’の部分列は空であってもよい 次に規則8°を使って為をλに変えて整理すると・目的 ものとする。 の｛1，0｝一右線形方程式系が次のように得られる。 κ1＝1物十〇為十〇石十〇為十λ 規則 物＝0κ1 公理則 為＝iκ1 1・κ。全λ κ・＝0為＋0石 20 κ1全1∼κo 梅二〇為十λ 書き換え則 3° xニ…＋（α＋β）y＋…→κ＝…＋α夕＋⑳＋… 8．2上昇型の変換法 40 κ：＝… 十〇碗夕十… → κ＝… 十α2十… （αキλ，βキλのとき） z全βy この節では・正規表現の再帰的定義による構成法 5・κ＝α・βy →κ＝ακ＋⑳ （定義3・1）に対応する上昇型の変換法を与える。 6・x＝…＋α・βy＋… →κ＝…＋⑳＋α2＋… まず・与えられたΣ一正規表現Rに対して・そのRを z合βy＋α2 解（ベクトルの第1成分）とするような（ΣUΣ゜）一右線 7・ κ＝＿＋x＋＿ →x＝＿＋＿ 形方程式を構成する方法を与える。そのため，Σ一正規表 8・ κ＝…＋y＋… →x＝…＋〈yの定義式 現を定義する定義3・1における（i）公理則および（ii）構 の右辺〉＋… 成則に対応する（Σ∪Σ゜）一右線形方程式の（i）公理則 （算法終） および（ii）構成則を次に与える。 上記の算法8．2で新しく変数が導入される規則は，公 ［補題8．2］ 理則1・と2・，構成則4・（連接の分離）と6°（閉包の再帰 （i）（公理則） 次の3つの方程式の解は’それぞれ 式変形）の場合だけである。従って次の補題が成り立っ。 φ，λおよびσεΣである。 ［κ1］：＝ ［φ］ ［箱］十 ［φ］ （8．7） ［補題8．1］ Σ一正規表現Rに算法8．2を適用して得 ［x1］＝［φ］［x1］＋［λ］ （8．8） ㌫㌶㌔麟㌫㌶蕊三 匡1＝1部1＋rll （8・9） 数を越えることはない。 （ii）（構成則）（ΣUΣ゜）一右線形方程式苫＝・4 X＋￠お よびy＝B夕＋dの最小解をそれぞれαおよびβとする ［例8．1ユ｛1，0｝一正規表現（10＋0・01）・0・を とき’次の3つの（ΣUΣ゜）一右線形方程式の最小解は・ 定義するΣ一右線形方程式を求める。 それぞれα㍉αβおよびα＋βである。 當1。＋。，。1）、。㌦ ；： ［：］一［1：二［，φ］］囹＋［ll （8・1・） ：：（10十〇＊0110κ1＋0＊01）㌶：： 1： ［；］一［：［劉［；1＋［1］ （8・11） 126 ［ヨ＝［1当ll1＋日（8・12）提8蟻i：C（ΣU 形方程式 出力 Rを定義する（Σ∪Σ゜）一右線形方程式 （証明） 方法 （i） 明らか。 （a）（逆ポーランド記法変換） （ii）前提より［4＊￠］1＝α・［β＊㎡］1＝β。これを基に・ 与えられたΣ一正規表現Rを逆ポ＿ランド記法： 上記3式の右辺の第1成分を求めると・それぞれ次が得 R’＝ρ、…ρゴ…ρ， られる・ に変換する．ここでρ、（樹はρ、εΣU｛φ山U｛＊，・，＋｝ 式（8・10）において・ である。 x＝（A＋［￠φ］）苫＋ピ （b）（（Σ∪Σ゜）一右線形方程式の構成） ∼x＝・4＊［￠φ］κ＋・4㌔ Σ一右線形方程式（または，それへのpointer）を，その ∼x＝［・4牢￠ φr・4＊￠ セルの内容とするpush・down stack Pを用い， Pを初期 ＝ αφ寧α 化したのち，入力ρ1，…，ρゴ，…，ρ，ごとに次の操作をP ：φ寧： に施こす。 ． （b1）（単項構成則の適用） ぼ の ＝ ： ρF＊のとき，Pをpop・upして得られる（Σ∪Σ゜）一右 線形方程式x＝ノ1苫＋￠1に対して変換式（8．10）を適用し， ゆえにz1ニκ1＋λニα＊α＋λ＝α＊ @ その結果をPにpush・downする。 式（8・11）において・ （b2）（二項構成則の適用） x＝Ax＋［・φ1醐 ρ、ニ．または＋のとき，Pを2回P。P。pして得られる2 ∼x＝・4＊［￠φ］B＊∂＝し4㌔φ］β＊㎡ つの（ΣUΣ゜）一右線形方程式x＝Ax＋erおよびyニβy −ll號一1¶ 爆㌘蕊：享；1たは（8・12）を適用し・ ゆえにκ1＝αβ。 （C）（出力） 式（8・12）において・ PをPOP・upする。 z1＝ε1x＋ε；y （算法終） κ＝・4x＋￠ 附録および補題8．2より算法8．3の正当性が保証され y＝By＋㎡ る。なお，算法8．3で得られる方程式は（Σ∪Σ゜）一右線 ゆえに z1＝κ1＋y1＝α＋β 形方程式である。これをΣ一右線形方程式に変換するには （証明終） 定理5．1（空語自由化）を用いればよい。 上記の補題82を用いることによって・与えられたΣ一 ［例8．2］算法8．3を用いてR＝（α＋λ）（b6）・の特性 正規表現Rに対して・1∼をその最小解（ベクトルの第1成 化（Σ∪Σ・）一右線形方程式を求める。 分）とするような（Σ∪Σ゜）一右線形方程式を求める算法 （a）Rの逆ポーランド記法はR’＝αλ＋b6．＊． であ が次のように求められる。 る。 （b） 2辺 （ΣUΣ゜）一右線形方程式 P 適用規制 127 ・ピトロ園＋日・・佃且（8・9） 苅 一一 ∼ …（7）幽 一λ・一λ κ1 − 一：一α：一 花 一 rLL物川 ▽ 二λλ x1 ｛8ユ2） ラリのでしエロドサぽロロラしづぷき ロロポラサ △ ÷ ﾉ c −一 一 （8．8） 十 λ κ1 a￨ 一一一 λ 固＝日［ズ1］＋［λ］ …（2）＝ κ1 ﾉ一一 一一 “一 ー：一一1一 石 λ （脚注》 i一一 κ1 @一α；一一一一 ・一一一 Pλ一一一 “一一一 沿黹ﾉ一一 κ4 一∼［聞1日1ト皿 十 λ 一一一 堰￨一カー ・一一一 堰￨一一λ 一 一一lc − 一 一 b［：H：こH：10＋一ω 細随⊥（8ユ1） （3） （4） （8．9） 得られた方程式倒は空語自由にするため，その係数行 列Aを次のようにLと、4’として分離する（44＝L十∠4〃）。 ・にトに二｝匡ト日一掴 一λλ一一一一 十十一一一一一 一一一一 ｛3） （4） （5） （8．9） L＝ κ1 一6トー 一⇒λ一 ■ ・一 ﾉ一一一 一一一一 ﾉ一一 κ1 十一一… 一一一一一一一 …⑥ ﾉ u一ぐ λ 13） ｛6） ｛8．11） 一一 @α 一 一 一一 ▽x1 一一 Pλ一＿＿ ズ1 λ ∠4’＝ 一トb−一 「一一λ一 ＊ 一ト ー （8，1◎） 一一一一一 Jー 一1一一一 ご △ 一；λ一一一 λ 一 一 一 c − 一 一 次に，系7．1．1よりL＋を求め，これを基に．L㌔4’およ びL㌔を求める。 ｛脚注）ここで▽と△を付けた変数為と石は補題6．2に よって等価である。従って△をつけた変数石を▽を付け た変数為に等置することによって消去する。以下同様。 128 ：H耽1＋田 （8・15） 一λ λ λ λ一＿ 一一一 ﾉ λ一 一 L＋＝ 一一一一 ﾉ一一 一一一一一一 ﾉ （ii）（単項構成則） 次のΣ一右線形方程式κ＝海＋ Cの解をαとするとき，次のΣ一右線方程式の解は，そ れぞれα＋およびα＊である。 κ＝（ノ4十￠ε1／4）κ十￠ （8．16） ［コ二胤晶北］＋［1］（8・17） 一一 ▲ ▽ L㌔4’＝ △ ｿ一一b− 一 一 α 一 一 一 一 一一一一一 一一一一一 一一一一一 a￨ a￨ a￨ ▽ 一 一 一 c − 一一 △ 一 一 一 c − 一一 ▽ △ とするとき，次の2つのΣ一右線形方程式の解は，それ ぞれαβおよびα十βである。 ［1］＝［：㌻1田＋［司 （8・18） x ＝ φ ノ1 （P 苫 十 c （8．19） ▲ △ ＝・4X＋Cおよびyニβy＋㎡の解をそれぞれαおよびβ 自1φ笥自ピ「 λ L・￠＝ ▽ （iii）（二項構成則）次の2つのΣ一右線形方程式：κ λ λ ここで▲はXlより到達可能 y φ φ 8 ㎡ でないことを示す。この場 合その変数は削除できる。 （第1報参照）。 （証明） （i）明らか。 ， （ii）式（8．16）に対して， x＝（、4十cε1A）x十￠ こうして方程式（8）は次のようになる。 ＝（、4・￠ε1、4）・、4㌔＝、4㌔（ε1ん4・τ）・ iHヨlil＋］ 1二：二1 e− ＝、4＊￠（ε1、4㌔）＊ （8．20） 補題8．2では，（Σ∪、Σo）一右線形方程式を得る規則を ．’，κ、＝ε1、4＊￠（ε1、4＊￠）＊＝αα＊＝α＋ 与えた。これを、Σ一右線形方程式に変換するには，空語 式（8．17）に対して， 自由化を行う必要があった。これに対して，次の定理8．1 x＝（、4十￠ε1、4）x＋e を用いれば，直接にΣ一右線形方程式を求めることがで ＝、4＊￠（ε1、4、4＊c）＊ きる。 ゆえに z1＝ε1／1／1＊c（ε1、4／1＊￠）＊十λ ［定理8・1］ 一（・1M・，）・一（（、IE。）・（ε1巫・，））・（ε1E，）・ （i）（公理則） 次のΣ一右線形方程式の解は，それ ＝（ε1E￠＋ε1、4、4＊￠）＊＝（ε1、4＊￠）＊ それφ・λおよびσεΣである。 ＝α・ ［・1］＝［φ］［・1］＋［φ］ （8．13） （iii）式（8・18）に対して・ 岡一［φ］［・1］＋［λ］ （8．14） x＝Ax＋・ε；（βy＋の ＝∠4x十cε｛y 129 ＝Ax＋cβ （c）（出力） ゆえに κ1＝ε1／rcβ＝αβ Pをpopupする。 式（8．19）に対して， （算法終） z、＝ε1（、4x十￠）＋ε；（By＋d） ［例8．3］算法8．4を用いてR＝（α＋λ）（bc）＊の特性化 ＝εlx＋εly＝κ、＋y、 Σ一右線形方程式を求める。 ＝α＋β （a）Rの逆ポーランド記法はR’＝畝＋bc・＊・であ （証明終） る。 上記定理8．1を用いることによって，与えられたΣ一 （b） 正規表現Rに対して，1∼を定義する，すなわちRを解 込±L Σ一右線形方程式 丑 適用規則 二蕊蕊右線形方程式を求め 吹tH：¶川㍗皿 （8．15） ［算法8．4］ Σ一正規表現のΣ一右線形方程式特性化 （上昇型，機械向き） λ ［x1］＝［一］［x1］＋［λ］…（2） 1（1）（2） （8．14） 入力 Σ一正規表現 R 出力 Rを定義するΣ一右線形方程式 ＋ ．竺． 一：一 α：一 一：一 α：一 方法 ▲ i／＋‖一 （a）（逆ポーランド記法変換） ▽ 与えられたΣ一正規表現Rを逆ポーランド記法： △ ’亘’ 1∼’＝ρ1… ρ‘… ρア ・ ：巖・こ一（・一一λ品一［：1−「¶：日；州皿 （1こ㌶㌶瓢へのP。㎞t百）を，その咽一日［：ト［1］蜘 セルを内容とするpush・down stack Pを用い， Pを初期 化したのち，入力ρ、，…，ρ‘，…，ρ。ごとに次の操作をP （3）（4） （8．15） に施こす。 ご1鷲貝巖のとき，＿形方程式 ¶＝：：じト細 （8・13）・（8・14）または（8・15）をそれぞれPにpush− @ 1（3）（4）（5）（8．15） downする。 曇饗璽騨：罐：li1一三墾i‖＋ （8．18） λ」 （b2）（二項構成則の適用） ’ ρ‘ニ・または＋のとき，・Pを2回pop・upして得られる 2つのΣ一右線形方程式： ∼ iト「ll匡1＋ヨ洞 x＝、4x＋￠およびy＝By＋㎡ にそれぞれ合成式（8．18）または（8．19）を適用し，そ の結果をPにpu由downする。 （3）（6） 130 ＊ ▽ ▲ △ △ ’ 3）安在，南，重松：“言語機械代数（第2報）Σ’一右線形方程式 1，”九州工大研究報告（工学），No．42， pρ433−9（1981−3）． 一1：H：lll：ト日仙）（7）・ぽ盈鴛1蝋蕊1元ご 式 5）安在弘幸1“半線形代数（第1報）言語機械代数として，”電子通 一［十にぷト1ヨー：；熱鞭襟雛蕊 generator，”Proc， of Int’1 Comp． Symp． ICS80 Vol II，Taiwan （￠）｛8）を出力する。 （1980−12）・ 10）安在，中村，潮崎，松原，上鍛治，積山：“言語処理系の自動 あとがき 生成システムLPG／1にっいて”・電子通信学会オートマトンと言 語研資， A】し？9−66（19？9−11）． 本稿（第8章）では，与えられた幾つか（または1つ） 11）Ah・， A V・and Ullman・JD：‘’The Theory of Parsing・ ・の正規親｝こ対して，それら（またはそれ）を解ベクh T「anslati°n and C°mpiW 1・乳P「enticeHall〈1972）’ ルのどれかの成分（または第1成分）に持つようなΣ 附録 演算式と演算算法 一右線形方程式を求める問題に対する解法を与えた。こ の問題は，与えられた正規言語に対し，それを受理する 算術式，論理式，正規表現，更にはプログラム言語な 有限オートマトンまたはそれを導出する右線形文脈自由 ど，一般に演算子（◎ρerator）と被演算子（⑩館砲d）の 文法を構成する問題に等価である。前稿・）（第7章）の問 宛からなる演算式（expression）は，次の3種またはそ 題がグラフ理論側とオートマトン理論側の両方から提起 れらの混合記法で表される。 された問題であったのに対して，この問題はオートマト （i）中間記法（infix notation） ：標準記法 ン理論側からのみ提起されたものであった。オートマト ｛ii）前置記法（prefix notation）：ポーランド記法 ン理論において，前稿は解析論であり，本稿は合成論で 爾 後置記法（p◎§丘ix notation）1逆ポーランド記法 ある。 本稿で示レた方法は工学的に極めて有用である。事実 この中で，圃の後置記法（逆ポーランド記法〉は，そ 既に発表した論文8），9）・1°）においてコンパイラの自動生成 れそれ書かれた式が，次に示すようにpush−down stack 論を与えたが，そこではこの方法を実用している。 を用いた機構で極めて自然に演算（評価または解釈）を 以上，すなわち第2，第3および第4報でII部Σ＊一右 行わさせることができる。 線形方程式論を終る。この簸部は既に発表した論文1）に 一一般に，後置記法の構文はBNFで次のように表せる。 その後の発展を加えて体系的に再編成したものである。 〈式〉：：＝〈被演算子＞ 1 〈式〉〈単項演算子＞ 1 〈式〉〈式〉〈二項演算子＞ 1 〈式〉〈式〉…〈式〉〈η項演算子〉 131 次に一般に，後置記法（で書かれた）式を読みこんで 演算（評価または解釈）を行う算法を示す。 ［算法8．5］後置記法式の演算 入力 後置記法式 R＝αbα2，…o‘，…伽 出力 Rの演算（評価または解釈）結果 方法 Pを初期化したのち，Rの先頭から1記号つつ αを読みこんで，次の（i）または（ii）を行い， Rを読み終えた のちPをpop−upする。 （i）α‘が被演算子ならばPにpush−downする。 （ii）佑がη項演算ならば， Pをη回pop−upしてη個 の被演算子を得，これに演算α‘を施し，得られた結 果をPにpush−downする。 （算法終） 算法8．5の（i）および（ii）において，被演算子や演算結果 をpush downする代りに，非終端記号の〈式〉をpush downするようにする。このとき，この算法は最右導出川 （righ−most derivation）に対する最左還元1D （left− most reduction）を行う上昇（bottom−up）型の構文解 析を行っていることがわかる。すなわち，上記算法8．5で は〈式〉の代りに，その評価値が対（〈式〉，〈評価値〉） として使用されている。従って次の定理が成りたつ。 ［定理8．2］算法8．5は，与えられた後置記法（で書かれ た）式に対して，その演算子に定義された演算（評価ま たは解釈）を正当に実行する。 従って，中間記法，前置記法または混合記法で書かれ た式を演算するには，それらを後置記法に変換したのち， 算法8．15を用いて演算を行えばよい。これを行う算法を 次に示す。 ［算法8．6〕一般の式の演算 入カ ー般の式 出力 式の演算結果 方法 次の手続きを行う。 （i）与えられた式を逆ポーランド記法に変換する。 （ii）（i）の変換結果に算法8．5を適用する。 〈算法終〉
© Copyright 2025 ExpyDoc
