Topcoder DFA

PROBLEM STATEMENT

A Deterministic Finite Automata (DFA) is a finite state machine with some number of states which we will call states 0 through N-1. For the purposes of this problem, state 0 is the start state. The DFA is then given a sequence of symbols from a finite alphabet (an alphabet might contain only '0' and '1', for example, or might be only lowercase letters). For each state, there is a transition for each symbol in the alphabet to some state (possibly the same state). Finally, some set of states are denoted as accept states. If the DFA is in one of the accept states after a sequence of symbols has been given to it, then it accepts that sequence of symbols, otherwise it rejects the sequence. For example, consider the simple DFA illustrated below:

The DFA starts in state 0, and a '1' causes it to switch from state 0 to state 1 and vice versa, while a '0' causes it to remain in the same state. Since state 0 is the only accept state, a sequence is accepted if, and only if, there are an even number of '1's. You will be given a DFA as a vector<string>, dfa. Element i of dfa will represent state i, and be formatted as a list of K integers separated by single spaces, where K is the number of symbols in the alphabet. Integer j of element i of dfa indicates the state that the DFA will end up in if it is currently in state i, and is given symbol j. A vector<int>, accept, indicates which states are accept states. Your task is, given the DFA specified by the input, return the minimum number of states required to build a new DFA that accepts the reverse of every sequence accepted by the input DFA. That is, the new DFA should accept a sequence s if, and only if, the input DFA accepts reverse(s).

DEFINITION

Class:DFAReversal Method:reverse Parameters:vector <string>, vector <int> Returns:int Method signature:int reverse(vector <string> dfa, vector <int> accept)

CONSTRAINTS

Each state in dfa will be reachable from the start state, state 0.
dfa will contain between 1 and 10 elements, inclusive.
Each element of dfa will contain between 1 and 10 integers separated by single spaces, with no extra leading zeros, inclusive.
Each element of dfa will contain the same number of integers.
Each integer in dfa will be between 0 and the number of elements in dfa-1, inclusive.
accept will contain between 0 and 10 elements, inclusive.
Each element of accept will be between 0 and the number of elements in dfa-1, inclusive.
No number will occur more than once in accept.

EXAMPLES

0)
{"0 1","1 0"}
{0}

Returns: 2

In this DFA, we switch states whenever we see the second symbol. Since we start in state 0, and it is our accept state, this DFA accepts all strings with an even number of occurrences of the second symbol. Therefore, if s is accepted by this DFA, reverse(s) is also.

1)
{"0 1",
 "0 0"}
{0,1}

Returns: 1

Everything is accepted, so we really only need one state.

2)
{"0 1",
 "0 2",
 "0 2"}
{2}

Returns: 4

This DFA accepts any sequence that ends with two occurrences of the second symbol.

3)
{"1 1",
 "2 2",
 "3 3",
 "4 4",
 "5 5",
 "6 6",
 "7 7",
 "9 8",
 "8 8",
 "9 9"}
{8}

Returns: 256

4)
{"0 0 0 0 0 0"}
{}

Returns: 1

Owen L. Astrachan

Last modified: Thu Jan 27 00:09:36 EST 2005