機械に、ある記号列 x を入力すると、ある記号列 y をもたらす。この機械には4つの規則がある。
規則Q Qx → x
（任意の記号列 x に対して、記号列 Qx は x をもたらす）
規則C x → y ならば、Cx → yQy
（x が y をもたらすならば、Cx は y の随伴 yQy をもたらす）
規則R x → y ならば、Rx → yy
（x が y をもたらすならば、Rx は yy、すなわち y の反復をもたらす）
規則V x → y ならば、Vx →y
（x が y をもたらすならば、Vx は y の反転をもたらす）
今回は、問18を解いていく。
問18 任意の記号列 y に対して、ある記号列 x で、
（解答）
まずは、
求める記号列 x は、
x →を満たす。x JKL ・・・・・①
反転のかたちがあるので、x は V からはじまる記号列として、x = Vx1 とすると、①は、
Vx1 → [と書ける。このとき、規則V の条件より、Vx1 ]JKL ・・・・・①'
x1 → LKJVx1 ・・・・・②とならなければならない。
問４より、CQyC → yCQyC であるので、この y = LKJV とすると、CQLKJVC → LKJVCQLKJVC が成り立ち、これは②の x1 を x1 = CQLKJVC としたときに一致する。
したがって、求める記号列は VCQLKJVC である。
（問９で求めた、RQyRQ → yRQyRQ を利用した VRQLKJVRQ も解答となる。）
いまの結果をあらためて規則V に沿ったかたちで明示的に書くと、「CQLKJVC は LKJVCQLKJVC をもたらすので、VCQLKJVC は CVJKLQCVJKL をもたらす」、つまり、
CQLKJVC → LKJVCQLKJVC であるので、ここで、記号列JKL を z とすると、LKJ は
VCQLKJVC → CVJKLQCVJKL ・・・・・③
CQと書ける。CQz VC →z VCQz VC であるので、VCQz VC → CVzQCVz ・・・・・③'
したがって、任意の記号列 y に対して、
（VRQ
（つづく）
0 件のコメント:
コメントを投稿