你能給我2個不同的語法輸出相同的一組字嗎？在一組輸出上的兩個不同語法
插圖：
鑑於在字母表{0,1}語法A和B，如果語法A可以產生字0101001，語法B可以爲好。如果語法B可以產生0101111，那麼語法A也可以。如果語法A不能產生01001，那麼B既不能。
但是這裏的事情是語法A和B彼此不同，即它們使用完全不同的算法。那麼他們產生的這組輸出不僅僅是另一個的一個合適的子集。說他們相應的一組輸出的含義必須具有相同的基數。可能它們的複雜程度不同，但沒關係。如果你願意的話，我會非常感謝你，如果你像字典的圖靈機一樣給我使用字母{0,1}的語法。
不知道這是可能的。如果A可以產生輸出a，那麼任一B都直接包含a或包含b和b'，短於a產生a。同樣的論點則適用於b（和b'） - 它直接在A中，或者在A中存在a和a'短於b中的a和b'。重複這個論點，最終你得到一個點，其中單個元素的長度爲1，所以你不能進一步分解它們，並且你必須在A和B中具有相同的元素。
燁。我也認爲這是不可能的。我只是想到了用於分割的歐幾里德算法，而不是像傳統的兩種不同的算法那樣分割，但是完全一樣。或者我正確地指出了這一點？ – 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-07-28 09:30:24