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. For those of you who are unfamiliar with the concept of deterministic finite automata, you may use the following information: A deterministic finite automata (DFA) is a 5-tuple, (S,Σ,T,s,A), consisting of • a finite set of states (S) • a finite set called the alphabet (Σ) • a transition function (T :S×Σ→S) • a start state (s ∈ S) • a set of accept states (A ⊆ S) Let M be a DFA such that M = (S,Σ,T,s,A), and X = x0x1 ...xn be a string over the alphabet Σ. M accepts the string X if a sequence of states, r0,r1,...,rn, exists in S with the following conditions:
2/2 Sample Input 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 Sample Output Case #1: No Case #2: Yes