你能给我两种不同的语法来输出相同的单词集吗？
插图：
给定字母表 {0,1} 上的语法 A 和 B，如果语法 A 可以产生单词 0101001，那么语法 B 也可以。如果语法 B 可以产生 0101111，那么语法 A 也可以。如果语法 A 不能产生 01001 那么 B 也不能。
但这里的问题是语法 A 和 B 彼此不同，即它们使用完全不同的算法。那么他们产生的输出集合不仅仅是另一个输出的适当子集。意思是说它们对应的一组输出必须具有相同的基数。可能它们具有不同的复杂性等级，但这没关系。如果可以的话，如果您能给我提供字母 {0,1} 上的语法，就像经典的图灵机一样，我将不胜感激。
不确定这是可能的。如果 A 可以产生输出 a，那么 B 要么直接包含 a，要么包含比 a 更短的 b 和 b'，从而生成 a。然后同样的论点适用于 b（和 b'）——它要么直接在 A 中，要么在 A 中存在比 b 短的 a' 和 a'' 来生成 b。迭代这个论点，最终你会得到单个元素长度为 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 -> {}