一组输出上的两种不同语法

Question

你能给我两种不同的语法来输出相同的单词集吗？

说明：

给定字母表 {0,1} 上的语法 A 和 B，如果语法 A 可以产生单词 0101001，那么语法 B 也可以。如果语法 B 可以产生 0101111，那么语法 A 也可以。如果语法 A 不能产生 01001，那么 B 也不能。

但这里的问题是语法 A 和 B 彼此不同，即它们使用完全不同的算法。那么它们产生的输出集不仅仅是另一个输出的真子集。意思是说它们相应的输出集必须具有相同的基数。也许它们具有不同的复杂性类别，但这并不重要。如果可以的话，如果您能给我字母表 {0,1} 的语法，就像经典的图灵机一样，我将不胜感激。

Answer 1

不确定这是否可能。如果 A 可以产生输出 a，则 B 要么直接包含 a，要么包含比 a 短的 b 和 b' 生成 a。同样的论点适用于 b（和 b'） - 它要么直接在 A 中，要么在 A 中存在比 b 短的 a' 和 a'' 生成 b。迭代此参数，最终到达各个元素长度为 1 的点，因此您无法进一步分解它们，并且 A 和 B 中必须具有相同的元素。

Answer 2

这个技巧可以吗？ 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 -> {}