Two-Dimensional Tree Recognizer

Automata as Input

The issue of treating automata as input was resolved using a set of tuples in a file. The following lines are 4-tuples, each representing a rule in the automaton. The first element of the tuple is the node's symbol, the second and third are the states of the left and right children, respectively, and the fourth is the state that should be assigned to the the node. There is an exception that must be resolved, however. The leaves of the tree have empty trees as children. To relsolve this, the first line of an automaton file contains a pair. The first element is the label of an empty tree, and the second element is the default state. Here is an automaton that will accept all strings over the alphabet {a,b} where |b| < 2.

0 ~
a 0 0 A
b 0 0 B
A A A A
A A B B
A B A B
B A A B

The Recognition Program

The tree recognizer inputs a tree as a string and an automaton and returns whether or not the string yield of that tree is licensed under the automaton. The algorithm uses a recursive method of assigning states to each node until the root node is assigned a state representing the final result of that instance of the recognition problem. Given a node, the algorithm uses the label of that node and the states of its children to determine what state should be assigned. If the states of the children are not yet known, the algorithm recurs to the children. At the beginning of the algorithm, only the states of the null children are known, so recursion will occur until a leaf is encountered. From that point, states can be assigned and the algorithm will work its way up the tree until it returns to the root node. The state of the root node determines the accepting or rejecting result.

The Algorithm

/* const qobj& rec(tree* root, const automaton& aut)
 * Recursively calculate the state of root, as computed by a tree-recognizing
 * algorithm.  Returns the state of root
 */
template<class sobj, class qobj>
const qobj& rec(tree<sobj,qobj>* root, const automaton<sobj,qobj>& aut)
{
  qobj lstate, rstate;
  
  if (root->left() == NULL)
    lstate = aut.get_nochild_state();
  else
    lstate = rec(root->left(), aut);

  if (root->right() == NULL)
    rstate = aut.get_nochild_state();
  else
    rstate = rec(root->right(), aut);

  root->set_state( aut.nextstate(root->label(), lstate, rstate) );
  return root->state();
}

[an error occurred while processing this directive]