面白い問題おしえて～な二十問目

面白い問題おしえて～ ..

629:１３２人目の素数さん
14/05/23 20:37:21.90
開き括弧'('と閉じ括弧')'のみからなる記号列
（ただし'('と')'が正しく対応付けられるもの）
があるとする。
この記号列のある部分に対し、
(X(Y)Z)→(XYZ)(XYZ)...(XYZ)
という置き換えを考える。
(X(Y)Z)の外側および内側の括弧はそれぞれ対応する括弧であるものとし、
X,Y,Zはそれぞれ任意の記号列（長さ0でもよい）とする。
(XYZ)(XYZ)...(XYZ)は、(XYZ)を任意個（0個でもよい）並べたものである。
このような置き換えを無限に繰り返し行うことは不可能であることを示せ。

次ページ

続きを表示

1を表示