Data Structure to represent a DFA

I was wondering, what would be the best data structure to represent a DFA?

I am looking at converti开发者_运维百科ng a regular expression to a DFA and make this particular functionality as a library in Java.

The main thing is that, each entity in the regex carries a set of value rather than a single string value like "car" . In my case , each entity would carry many properties like {car, Honda, 4x4, sedan, ... } (Though I am not searching for cars, this is just an example.)

Any suggestions?

---

If I understand your question correctly you want to have a matching/filtering library for an arbitrary regular language over an alphabet with dynamic types? Going with your car example, I'd imagine you'd want to be able to create an expression in order to match over a List where all Cars (have the color red, have between 2 and 6 Passengers and each Passenger is between 8 and 88 years of age) or (have 1 Passenger).

Coincidentally I've been looking for something like that myself (for document validation) and the closest I could get was Jing; A Java RELAX-NG library. Unfortunately, the alphabet in Jing consists out of XML nodes so it didn't solve my problem. At the moment I'm attempting to write a library myself which does just this (matching against regular languages over an arbitrary type of alphabet), based on the pattern matching in Jing. If you like to help with this, please let me know ;).

---

A web search will yield some examples of DFAs in Java. However, the best representation depends on your specific application requirements; e.g. how your application is going to use the DFAs. I think you need to work this out for yourself.

---

I'm sure this answer won't be useful to the original question because of the data, but if anyone happens across this from google...

DFA's and NFA's can be stored as State transition table's, you then perform a parse by moving thought the table following the links as such.