*
The moose likes Java in General and the fly likes Which data structure to use for making a DFA Machine Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Which data structure to use for making a DFA Machine" Watch "Which data structure to use for making a DFA Machine" New topic
Author

Which data structure to use for making a DFA Machine

Gaurav Chikara
Ranch Hand

Joined: Jun 09, 2000
Posts: 410
Hi
I have been looking at all previously posted queries but didn't found any clue. I have a set of strings example {he,she} I have to make a DFA machine such that start state is 0
And for word he
on input symbol h next state is 1
on input symbol i next state is 2
on input symbol i next state is 3
Similary for word she
on input symbol s next state is 4
on input symbol s next state is 5
on input symbol s next state is 6
I need a data structure to store this information so that I can use ot to simlaute a Determinisitc Finite Automota Machine
Initially I thought trees but I still am confused whether they are the right choice.Has any one got any ideas on it then Pleease help
Thanks in advance


SCJP,SCWCD,SCBCD<br />If Opportunity doesn't knock then build the door
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

Please don't post your queries to more than one forum. For your convenience, I've deleted the other copy of this post.


[Jess in Action][AskingGoodQuestions]
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

A DFA is a generalized directed graph: each node can have an arbitrary number of transitions to other nodes, and the transitions themselves are non-trivial (i.e., there's a condition associated with each one.) There's no standard Collection class that supports this kind of graph directly, so your options are to either implement your own Node and Transition classes, or find them on the 'Net. You've got a million choices in the latter case; I did a quick Google search and found this one, for example.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Man, I got a nasty error trying to post a reply to the msg you deleted! Still in my clipboard:

Error
An error has occured:
Tried to open zero sized thread 007347 in forum 1 at /home/vhost1/saloon.javaranch.com/vroot/cgi-bin/ubb/ubb_lib_files.cgi line 762.
Please inform the board administration of this error so that they may fix the problem. Thank you!

Guess you can ignore it now.
My favorite parsing tree story is this Ternary Search Tree. Wait for the applet to load and see how fast it is. Amazing. Don't try to pass it off as your own homework!
[ April 11, 2004: Message edited by: Stan James ]
[ edited to change code to quote -ds ]
[ April 11, 2004: Message edited by: Dirk Schreckmann ]

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Gaurav Chikara
Ranch Hand

Joined: Jun 09, 2000
Posts: 410
Thanks all for your replies but they all require AWT API's which I don't need as I don't intened to use applets
Anyway thanks for the ideas
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
A DFA has a set of states, an alphabet, a function that maps a state and an input symbol onto a new state, a starting state, and a list of accepting states. The most direct way (although not the prettiest way) to implement it would be as follows:

The usage would look like this:

For an example of a DFA that does some computation at various transitions, see this thread (which contains code for a DFA tokenizer).
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
BTW: That TST thing used AWT / Applet to demonstrate, but the tree itself has no user interface at all.
Here's a slightly (!) advanced idea for handling state. Make a class for each state that knows what characters it will accept and what next state they should trigger.

Lots of typing, but hardly a method over 3 lines, which may be a kool thing in some people's book.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Which data structure to use for making a DFA Machine