3

Good evening,

I am searching for an elegant solution to implement a transition table (Specifically, for a universal pushdown automaton) that uses several discrete values for a given transition. They say a picture is worth a thousand words so here is part of my table:

State    InputSymbol    StackSymbol   Move(NewState, Action)
------------------------------------------------------------
  0           a              Z0           (0, push)
  0           a              a            (0, push)
  0           a              b            (0, pop)
  0           b              Z0           (1, push)
  ...

Now, I have considered multi-dimensional arrays, ArrayLists of ArrayLists, and other solutions of the sort but all seem rather brutish. This is further complicated by the fact that every possible combination of my three symbols (a, b, and Z0) is not represented in the table.

I have been contemplating using a HashMap, but I am not entirely sure how to make this work with multiple key values. I was considering concatenating all three symbols together and using the resultant string as my key but that, too, seems less than elegant.

And, for the record, this is homework but actually giving an elegant solution is not strictly required. I just enjoy good code.

Thank you in advance for your assistance.

3 Answers 3

4

Make a class like this:

 class Key{
    int state;
    char inputSysmbol;
    String StackSymbol;
    }

Then use the map Map<Key,Move>.

Make a class for Move just like above and don't forget to override hashcode and equals method in both classes.

2
  • Ah, so the key to this (pardon the pun) is encapsulating all of my data and then overriding hashcode and equals. Equals is pretty straight forward, it seems, but how would I implement a robust hashcode that is still quick? Definitely going to make my key objects immutable (awesome link, btw). Ideally, I would like to be able to extend my inputs from single characters into strings. I assume there isn't a much simpler way to do this then a digest algorithm? Commented Nov 17, 2010 at 17:03
  • @phobos51594:For hashcode implementing take a look into the book Effective Java.
    – Emil
    Commented Nov 17, 2010 at 18:26
1

Encapsulate {State, InputSymbol, StackSymbol} in an object. Then, use the "hashcode()" of the object as the key for your hash table. For more information regarding hash codes see Doc.

0

Take a look on MultiHashMap from Jakarta commons collections framework. http://commons.apache.org/collections/api-release/org/apache/commons/collections/MultiHashMap.html

Unfortunately jakarta collection framework is not parametrized, i.e. does not support generics, so you will have to cast you your specific type.

Other solution is to implement something similar your self. Create class Move that holds your data. Create class Table that encapsulate the logic. This class may contain a list (better LinkedList) of Moves and N maps: Map> stateIndex Map> inputSymbolIndex etc, etc.

implementation of add method is trivial. Implementation of get is more interesting:

public Move get(Integer state, Character inputSymbol, StackSymbol stackSymbol) {
    List<Move> stateList = stateIndex.get(state);
    List<Move> inputSymbolList = stateIndex.get(inputSymbol);
    List<Move> stackSymbolList = stateIndex.get(stackSymbol);

    Set<Move> result = new HashSet<Move>(stateList);
    result.retainAll(inputSymbolList);
    result.retainAll(stackSymbolList);

    if (result.size() > 1) {
        throw new IllegalStateException("Unique constraint violation");
    } 
    return  result.size() == 0 ? null : result.interator().next();
}
1
  • Hm, definitely something I had not considered before. Out of curiosity, what would the time complexity for a get() be? The multiple list operations seem like they would be rather expensive. Commented Nov 17, 2010 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.