在一组输出上的两个不同语法

你能给我2个不同的语法输出相同的一组字吗？在一组输出上的两个不同语法

插图：

鉴于在字母表{0,1}语法A和B，如果语法A可以产生字0101001，语法B可以为好。如果语法B可以产生0101111，那么语法A也可以。如果语法A不能产生01001，那么B既不能。

但是这里的事情是语法A和B彼此不同，即它们使用完全不同的算法。那么他们产生的这组输出不仅仅是另一个的一个合适的子集。说他们相应的一组输出的含义必须具有相同的基数。可能它们的复杂程度不同，但没关系。如果你愿意的话，我会非常感谢你，如果你像字典的图灵机一样给我使用字母{0,1}的语法。

来源

2010-07-28 neilmarion

非常像功课 – 2010-07-28 09:30:24

不知道这是可能的。如果A可以产生输出a，那么任一B都直接包含a或包含b和b'，短于a产生a。同样的论点则适用于b（和b'） - 它直接在A中，或者在A中存在a和a'短于b中的a和b'。重复这个论点，最终你得到一个点，其中单个元素的长度为1，所以你不能进一步分解它们，并且你必须在A和B中具有相同的元素。

来源

2010-07-28 09:25:28

烨。我也认为这是不可能的。我只是想到了用于分割的欧几里德算法，而不是像传统的两种不同的算法那样分割，但是完全一样。或者我正确地指出了这一点？ – neilmarion 2010-07-28 09:54:34

不完全 - 欧几里德算法给出两个不同数字的GCD，这里我们有一个元素，我们试图以不同的方式分解它。更像是找到相同数字的两个不同的素因数。但是我怀疑证据类似。 – 2010-07-28 10:17:10

这个技巧行吗？可以构造类型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 -> {}

来源

2010-11-20 00:46:09 Ante

在一组输出上的两个不同语法

回答

相关问题