同じ単語セットを出力する 2 つの異なる文法を教えてください。
図：
アルファベット {0,1} に対する文法 A と B が与えられた場合、文法 A が単語 0101001 を生成できる場合、文法 B も同様に生成できます。文法 B が 0101111 を生成できる場合、文法 A も同様に生成できます。そして、文法 A が 01001 を生成できない場合、B も生成できません。
しかし、ここで重要なのは、文法 A と B が互いに異なるということです。つまり、まったく異なるアルゴリズムを使用しています。次に、それらが生成する出力のセットは、他の出力の適切なサブセットではありません。つまり、対応する出力セットは同じカーディナリティを持つ必要があります。おそらくそれらは複雑度のクラスが異なりますが、それは問題ではありません。よろしければ、古典的なチューリング マシンのように、アルファベット {0,1} に関する文法を教えていただければ幸いです。
これが可能かどうかはわかりません。A が出力 a を生成できる場合、B は a を直接含むか、a を生成する a よりも短い b と b' を含みます。次に、同じ引数が b (および b') に適用されます。これは、直接 A に存在するか、b を生成する A に b よりも短い a' および a'' が存在するかのいずれかです。この引数を反復すると、最終的に個々の要素の長さが 1 になるポイントに到達するため、それらをさらに分解することはできず、A と B の両方に等しい要素が必要です。
このトリックは大丈夫ですか？タイプの文字0*n1*m列 (例: 000000111) は、左から右に作成できます。
A
A -> 0A
A -> B
B -> 1B
B -> {}
右から左へ：
B
B -> B1
B -> A
A -> A0
A -> {}
中から:
AB
A -> A0
A -> {}
B -> 1B
B -> {}