機械に、ある記号列 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 ならば、Rx →y
（x が y をもたらすならば、Vx は y の反転をもたらす）
前回の問題のなかの、問12から16までの解答を以下に記してみる。
＊＊＊＊＊
問12 それ自身の反転をもたらすような記号列を見つけよ。
（解答）
求める記号列を x とすると、
x →を満たす記号列 x を探す。x ・・・・・①
x は V からはじまる記号列となるため、x = Vx1 とすると、①は、
Vx1 →と書ける。（反転を表す矢印←がかかる範囲を明確にするために[]をつけた。）[Vx1] ・・・・・①’
このとき、規則V の条件より、
x1 → Vx1 ・・・・・②とならなければならない。
任意の記号列 y に対して、CQyC → yCQyC であるので（問４参照）、y = V とすると、CQVC → VCQVC となり、②を満たす。
求める記号列は x であるため、
x = Vx1 = VCQVCまた、問11より、任意の記号列 y に対して、RQyRQ → yRQyRQ であるので、CQyC → yCQyC のときと同様に、VRQVRQ もそれ自身の反転をもたらす。
∴それ自身の反転をもたらす記号列は VCQVC
＊＊＊＊＊
問13 それ自身の反復の反転をもたらすような記号列を見つけよ。
（解答）
求める記号列を x とすると、
x →を満たす記号列 x を探す。[xx] ・・・・・①
x は V からはじまる記号列となるため、x = Vx1 とすると、①は、
Vx1 →と書ける。このとき、規則V の条件より、[Vx1Vx1] ・・・・・①’
x1 → Vx1Vx1 ・・・・・②とならなければならない。
②は反復のかたちであるので、x1 は R からはじまる記号列。x1 = Rx2 とすると、②は、
Rx2 → VRx2VRx2 ・・・・・②’と書ける。このとき、規則R の条件より、
x2 → VRx2 ・・・・・③とならなければならない。
任意の記号列yに対して、CQyC → yCQyC であるので、y = VR とすると、CQVRC → VRCQVRC となり、③を満たす。
求める記号列は x であるため、
x = Vx1 = VRx2 = VRCQVRCまた、問11より、任意の記号列 y に対して、RQyRQ → yRQyRQ であるので、CQyC → yCQyC のときと同様に、VRRQVRRQ もそれ自身の反転をもたらす。
∴それ自身の反復の反転をもたらす記号列は VRCQVRC
＊＊＊＊＊
問14 それ自身の随伴の反転をもたらすような記号列を見つけよ。
（解答）
求める記号列を x とすると、
x →を満たす記号列 x を探す。[xQx] ・・・・・①
x は V からはじまる記号列となるため、x = Vx1 とすると、①は、
Vx1 →と書ける。このとき、規則V の条件より、[Vx1QVx1] ・・・・・①’
x1 → Vx1QVx1 ・・・・・②とならなければならない。
②は随伴のかたちであるので、x1 は C からはじまる記号列。x1 = Cx2 とすると、②は、
Cx2 → VCx2QVCx2 ・・・・・②’と書ける。このとき、規則R の条件より、
x2 → VCx2 ・・・・・③とならなければならない。
任意の記号列yに対して、CQyC → yCQyC であるので、y = VC とすると、CQVCC → VCCQVCC となり、③を満たす。
求める記号列は x であるため、
x = Vx1 = VCx2 = VCCQVCCまた、問11より、任意の記号列 y に対して、RQyRQ → yRQyRQ であるので、CQyC → yCQyC のときと同様に、VCRQVCRQ もそれ自身の反転をもたらす。
∴それ自身の随伴の反転をもたらす記号列は VCCQVCC
＊＊＊＊＊
問15 それ自身の反転の随伴をもたらすような記号列を見つけよ。
（解答）
求める記号列を x とすると、
x →を満たす記号列 x を探す。x Qx ・・・・・①
x は C からはじまる記号列となるため、x = Cx1 とすると、①は、
Cx1 →と書ける。このとき、規則C の条件より、[Cx1] Q[Cx1] ・・・・・①’
x1 →とならなければならない。[Cx1] ・・・・・②
②は反転のかたちであるので、x1 は V からはじまる記号列。x1 = Vx2 とすると、②は、
Vx2 →と書ける。このとき、規則V の条件より、[CVx2] ・・・・・②’
x2 → CVx2 ・・・・・③とならなければならない。
任意の記号列yに対して、CQyC → yCQyC であるので、y = CV とすると、CQCVC → CVCQCVC となり、③を満たす。
求める記号列は x であるため、
x = Cx1 = CVx2 = CVCQCVCまた、問11より、任意の記号列 y に対して、RQyRQ → yRQyRQ であるので、CQyC → yCQyC のときと同様に、CVRQCVRQ もそれ自身の反転をもたらす。
∴それ自身の反転の随伴をもたらす記号列は CVCQCVC
＊＊＊＊＊
問16 それ自身の随伴の反転の反復をもたらすような記号列を見つけよ。
（解答）
求める記号列を x とすると、
x →を満たす記号列 x を探す。[xQx] [xQx] ・・・・・①
x は R からはじまる記号列となるため、x = Rx1 とすると、①は、
Rx1 →と書ける。このとき、規則R の条件より、[Rx1QRx1] [Rx1QRx1] ・・・・・①’
x1 →とならなければならない。[Rx1QRx1] ・・・・・②
②は反転のかたちであるので、x1 は V からはじまる記号列。x1 = Vx2 とすると、②は、
Vx2 →と書ける。このとき、規則V の条件より、[RVx2QRVx2] ・・・・・②’
x2 → RVx2QRVx2 ・・・・・③とならなければならない。
③は随伴のかたちであるので、x2 は C からはじまる記号列。x2 = Cx3 とすると、③は、
Cx3 → RVCx3QRVCx3 ・・・・・③’と書ける。このとき、規則C の条件より、
x3 → RVCx3 ・・・・・④とならなければならない。
任意の記号列yに対して、CQyC → yCQyC であるので、y = RVC とすると、CQRVCC → RVCCQRVCC となり、④を満たす。
求める記号列は x であるため、
x = Rx1 = RVx2 = RVCx3 = RVCCQRVCCまた、問11より、任意の記号列 y に対して、RQyRQ → yRQyRQ であるので、CQyC → yCQyC のときと同様に、RVCRQRVCRQ もそれ自身の反転をもたらす。
∴それ自身の随伴の反転の反復をもたらす記号列は RVCCQRVCC
＊＊＊＊＊
（つづく）
0 件のコメント:
コメントを投稿