1接受与拒绝
机器只有"通过"房接受。若读完停在"没牌子"的房，结果是接受还是拒绝？
计算机原理 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2数灯亮几次
判断"按了双数次开关没有"，最少需要几个状态？
3确定的机器
某状态遇到"a"有两条箭头分别通往不同房间，这机器还"确定"吗？
4不确定的机器
分身走了3条路，其中1条到"通过"房。这串字被接受吗？
5猜一条路
走迷宫时如果每个岔路都能猜对方向，会发生什么？
6两种其实一样
不确定机器和确定机器，谁"能解决的问题"更多？
7什么是模式
用一句话描述"三个字母的英文单词"这个模式。
8正则表达式
想描述"以字母a开头"，你觉得暗号里该有哪个字？
9星号能重复
"b星号"能匹配"bbb"吗？能匹配空字符串吗？
10或者与连接
想匹配"cat或dog"，该用哪一招？
第 1 页 · 背面（答案）
参考答案（家长）：2个（单次、双次），每按一次就在两者间翻转。
参考答案（家长）：拒绝。
参考答案（家长）：接受，只要有一条路成功即可。
参考答案（家长）：不确定了，因为同一个字有多个走法。
参考答案（家长）：一样多；能力相同，只是所需状态数和快慢不同。
参考答案（家长）：一路直达出口，永不走冤枉路。
参考答案（家长）：开头写上"a"，表示第一个字必须是a。
参考答案（家长）：由正好3个英文字母组成的串，如"cat""dog"。
参考答案（家长）：用"或者"，写成 cat｜dog 那样。
参考答案（家长）：都能；星号表示0次或多次，"bbb"是3次，空是0次。
第 2 页 · 正面（题目）
11正则就是机器
正则和有限自动机，谁的"表达能力"更强？
12什么是语言
"所有以0结尾的数"是不是一种语言？举一个属于它的串。
13文法是造句法
机器负责检查，那谁负责按规则生成句子？
14用规则生句子
用上面的规则，还能拼出哪两句？
15递归的规则
"列表→一个数,列表"这种规则为什么能造出很长的列表？
16语言有难有易
判断"是不是双数"简单，为什么它对有限自动机不难？
17规则的层级
往上爬一层，机器的能力是变强还是变弱？
18什么是栈
往栈里依次放1、2、3，第一个拿出来的是几？
19括号要配对
")("的左右括号数量相等，它是正确的括号串吗？
20栈帮忙记账
用栈处理"(())"，读完后栈里还剩东西吗？
第 2 页 · 背面（答案）
参考答案（家长）：是；如10、20、100都属于它。
参考答案（家长）：一样强，二者能描述的模式完全相同。
参考答案（家长）：还能拼出"小猫跳""小狗跑"，共4句。
参考答案（家长）：文法（造句规则）。
参考答案（家长）：只需记"单/双"两个状态来回翻，房间够用，所以不难。
参考答案（家长）：因为规则里又用到了"列表"自己，可以一直套下去，越造越长。
参考答案（家长）：3（最后放的最先拿）。
参考答案（家长）：变强，能认识更多更复杂的语言。
参考答案（家长）：不剩，栈正好空，说明括号正确。
参考答案（家长）：不是；先出现了关括号，没有对应的开括号，顺序错了。
第 3 页 · 正面（题目）
21栈自动机
栈自动机比有限自动机多了什么帮手？
22有限机记不住
括号最多能嵌套多少层？这为什么难倒有限自动机？
23无限的纸带
纸带和栈相比，用起来哪个更自由？
24图灵机
图灵机由哪两大部分组成？
25读写与移动
图灵机一步能做哪三件事？
26图灵机很强
图灵机能算而普通电脑不能算的事多吗？
27一台顶所有
手机装不同的APP能干不同的事，这和"万能机器"是一个道理吗？
28程序就是机器
程序里的"代码"对应图灵机的什么？
29能算与不能算
"可计算"大概是什么意思？
30数不清的问题
程序数得清，问题数不清，这说明了什么？
第 3 页 · 背面（答案）
参考答案（家长）：任意多层，没有上限；有限的房间数记不下无上限的深度。
参考答案（家长）：多了一个栈，可以当会变大的记忆本用。
参考答案（家长）：一个有限的状态控制器，加一条无限长、可读可写的纸带。
参考答案（家长）：纸带更自由，能随意左右移动、任意读写，栈只能一头进出。
参考答案（家长）：没有；凡电脑能算的图灵机都能算，能力相同，图灵机只是更慢更笨。
参考答案（家长）：读一格、改写这一格、向左或向右移动一格（同时换状态）。
参考答案（家长）：对应转移规则（机器该怎么一步步动作的规矩）。
参考答案（家长）：是；APP就像喂给机器的规则，一台硬件靠换程序完成各种任务。
参考答案（家长）：程序不够分，必然存在没有任何程序能解决的问题。
参考答案（家长）：存在一台机器/程序，对任何输入都能一步步算出正确答案。