给定两个确定性有限状态自动机(DFA),判断 和 是否等价(即对于任意输入串,输出都一致)。
输入有若干组数据,对于每一组输入数据:
第一行一个正整数 表示字符集大小。
接下来描述 和 ,对于每一个 DFA:
第一行一个整数 表示状态数。
接下来 行,第 行有 个数 , 表示状态 是否为终态,若 表示状态 是终态,否则不是; 表示状态 通过字符 转移到状态 ,若 则表示无此转移边。
对第 组数据,输出单独一行 Case #i: Yes 或者 Case #i: No 表示第 组数据中两个 DFA 是否等价。
Case #i: Yes
Case #i: No
2 3 1 -1 1 0 -1 2 0 -1 0 2 1 -1 1 0 -1 0 3 4 1 -1 -1 1 1 -1 -1 2 1 -1 -1 3 1 -1 -1 1 2 1 -1 -1 1 1 -1 -1 0 0
Case #1: No Case #2: Yes
,。