• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Which data structure to use for making a DFA Machine

 
Ranch Hand
Posts: 413
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 413
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Paper jam tastes about as you would expect. Try some on this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic