A DFA is a state transition model that diagramatically looks like the following:
'po:purchaseOrder' (Start)--"billTo"-->(1)--"shipTo"-->(2)--+--"items"-->(Finish1) '--"po:comment"-->(4)--"items"-->(Finish2) 'billTo' (Start)--"first_name"-->(1)--"last_name"-->(2)--"city"-->(3)--"state"-->(4)--"zip"-->(Finish) 'shipTo' (Start)--"first_name"-->(1)--"last_name"-->(2)--"city"-->(3)--"state"-->(4)--"zip"-->(Finish) 'items' (Start)--"item"-->(Finish)--"item"--. ^ | '-----<<------'Each element (whether global or local) is uniquely identified. All the element tagnames allowed within the parent defines an 'alphabet' of valid content. Grand-children are irrelevant to the state transitions; the data structure can be built independently for each level in the schema model.
Two properties of a DFA are that every state has exactly one non-empty entry, and there are no state transitions on the empty input. Hence "deterministic" in the name, for any given state and input, there are either 0 or 1 state transitions possible.
A state transition matrix is created by treating the schema as a regular expression
according to the following mapping, where e
is an element in a complex type
and a
is an attribute:
0..unbounded ==> e*
1..1 ==> e
by itself (one instance)1..unbounded ==> e+
0..1 ==> e?
choice ==> ( e1 | e2 | e3 )
sequence ==> e1 e2 e3
any ==> sequence
Additional uses:
search the data structure to determine where we match valid states. Then perform expansion on the missing elements as needed to bring the model into a correct state.
DFA can be augmented or parallel table created to enable rapid searches from the parent to all its children.