use*_*807 10 string finite-automata
Marvin Minsky在口语考试中问我以下问题:
作为蚂蚁行走,它每次执行步骤时都会打印二进制数(例如,101).什么是最小长度,以数字为单位,二进制数可以是什么,可以告诉蚂蚁行进的方向而不查看字符串的开头或结尾？蚂蚁告诉你二进制数.
示例:蚂蚁的二进制数为101,因此,蚂蚁会留下如下所示的路径:101101101101101101101.请注意,无法确定蚂蚁的行进方式.因此,这个特定的数字不起作用(但可能有三位二进制数).
示例:蚂蚁的二进制数是011,因此,蚂蚁留下如下所示的踪迹:011011011011011011.再次,没有办法在不查看字符串末尾的情况下判断蚂蚁的行进方式.
这个问题的答案是什么？请注意,答案不仅仅是二进制数的一个例子.答案需要包括一个证明,即长度小于n-1的二进制数将起作用,其中n是有效的示例二进制数的长度.详尽的枚举证明是可以的,但令人不快.:)
另一种方法是偏离二进制数.将问题重新描述为"如果允许使用任意数量的唯一符号,那么最短的可能模式是什么？"
这里的答案是3(例如A; B; C或#;&; @),因为2不起作用.因此,当你有一个像ABC这样的模式时,蚂蚁正朝着哪个方向行走.
要么...... CABCABCABCABCAB ......(从左到右)或...... CBACBACBACBACBA ......(从右到左)
现在,我们需要在Ternary(base-3)中编写3个符号模式需要多少个二进制数字？
两个二进制数字允许您编写单个四元(基数为4)的数字,这是第一个高于或等于3的基数.
因此:(每符号2位数)乘以(3个符号)= 6个二进制数字.