1493: 有穷自动机

自动机理论是理论计算机科学中的重要内容。实际的计算机相当复杂，很难直接对它们建立一个易于处理的数学理论，因此在理论计算机科学中采用称为计算模型的理想计算机来描述。有穷自动机是最简单的计算模型。

有穷自动机M是一个5元组(Q，∑，δ，q0，F)，其中
1) Q是一个有穷集合，称为状态集；
2) ∑是一个有穷集合，称为字母表；
3) δ：Q×∑→Q是转移函数；
4) q0∈Q是起始状态；
5) F是Q的子集，是接受状态集。

例如，图1所示的有穷自动机M1，它有3个状态，因此Q = { q1, q2, q3 }，起始状态用一个指向它的无出发点的箭头表示，因此M1中，q1是起始状态。带有双圈的状态表示接受状态，因此M1中，q2是接受状态，因此，F = { q2 }。从一个状态指向另一个状态的箭头称为转移。在M1中，字母表δ = { 0, 1 }。在M1中，如果M1处于q1状态，此时输入符号1，则转向状态q2。
 

当自动机接收到字母表上的一个字符串，如“1101”时，它处理这个字符串并产生一个输出。输出是接受或拒绝。例如在M1中，如果输入字符串“1101”，则M1从起始状态q1出发，读入字符串中第1个字符1，转向q2；然后读入字符1，转向q2；然后读入字符0，转向q3；最后读入字符1，转向q2。q2是接受状态，因此M1接受字符串“1101”。

但是，如果输入的字符串是“11000”，M1最终停在q3，因此M1不接受字符串“11000”。

稍加分析可以得出结论，M1接受以1结尾的任何0、1串，以及在最后一个1后面有偶数个0的任何0、1字符串。任给一个0、1串，M1将得出接受或者拒绝的结论。

在本题中，给定一个自动机M1，如图2所示。在M2中，Q = { s, q1, q2, r1, r2 }；δ = { a, b }；起始状态为s；接受状态集F = { q1, r1 }；M2中的每一对转移在图2中用箭头表示。本题要求解的是，给定字母表δ上的任何一个字符串，判定M2接受还是拒绝。

输入文件中包含多个测试数据。每个测试数据占一行，为字母集{ a, b }上的一个字符串，字符串的长度最长可达1000。输入文件最后一行为0，代表输入结束。

对输入文件中的每个测试数据所表示的字符串，如果能被有穷自动机M2识别，则输出yes，否则输出no。

aaaaabbbaaabaabababababababababaababaaba
bababaaaabbbaaababababababaaaabaaaa
0

yes
no