Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Which data structure to use for making a DFA Machine

 
Gaurav Chikara
Ranch Hand
Posts: 412
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please don't post your queries to more than one forum. For your convenience, I've deleted the other copy of this post.
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Gaurav Chikara
Ranch Hand
Posts: 412
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic