Problem H. History of Languages
时间限制 5000 ms 内存限制 32 MB
We are examining two specific classes of languages (a possibly infinite set of
strings) in this problem. Fortunately (or maybe unfortunately), we are not given the strings contained in each language directly, rather we are given two deterministic finite automatons that describe such languages.
Your task here is simple: to determine if the languages described by the two automatons are the same.
strings) in this problem. Fortunately (or maybe unfortunately), we are not given the strings contained in each language directly, rather we are given two deterministic finite automatons that describe such languages.
Your task here is simple: to determine if the languages described by the two automatons are the same.
输入数据
There are multiple test cases in the input file.
The first line of each test case is one integer, T ( 2 ÷ T ÷ 26), the size of the alphabet. In each test case, the description of automaton A comes before that of automaton B. The description of each automaton starts with one line containing N (1 ÷ N ÷ 2000 ), the number of states in the automaton, followed by N lines, each line of the format: F, X 0, X 1, ˇ, X T-1,
,-1 ÷ X
i < N). If F = 1, then the state is an accepting state; also, if X
i = -1, it means that the state has no corresponding transition available for character i. The start state of both finite automatons will always be state 0.
Two successive test cases are separated by a blank line. A case with a single 0 indicates the end of the input file, and should not be processed by your program.
The first line of each test case is one integer, T ( 2 ÷ T ÷ 26), the size of the alphabet. In each test case, the description of automaton A comes before that of automaton B. The description of each automaton starts with one line containing N (1 ÷ N ÷ 2000 ), the number of states in the automaton, followed by N lines, each line of the format: F, X 0, X 1, ˇ, X T-1,
,-1 ÷ X
i < N). If F = 1, then the state is an accepting state; also, if X
i = -1, it means that the state has no corresponding transition available for character i. The start state of both finite automatons will always be state 0.
Two successive test cases are separated by a blank line. A case with a single 0 indicates the end of the input file, and should not be processed by your program.
输出数据
For each test case, please print “Yes” if the two languages described by the
automatons are equivalent; output “No” otherwise.
automatons are equivalent; output “No” otherwise.
样例输入
复制
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$ Mathjax font initiator $
提交
请先 登录