• Post Reply Bookmark Topic Watch Topic
  • New Topic

A DFA string search algorithm  RSS feed

 
Abeer El-shaer
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
JavaProjMy teacher gave me a project i can't understand ho does it work or how to solve it even he want meto enter a DFA and then enter a text and see if it's accepted or not and the table is from the file that i loaded from my pc as i see now i don't know how to begin what the first step how does all of these things work just can't understand how con we tell him that if we gave it a then go to q1 from example all that logic can't imagine it if anybody have ever seen these thing just the steps or tell what is this how can i relate them to each other "the logic".
thanks rom now
 
Stephan van Hulst
Saloon Keeper
Posts: 7969
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Abeer,

An easy way to model a DFA is to create an object for each state, and that state keeps track of what symbols lead to what other states. Then, you can give them a method that takes a symbol, and returns the correct state it leads to. Finally, you can give them a method that takes a String, and recursively resolves the symbols in the String one at a time.

Start by creating a class called State, and giving it a way to add transitions between it and another state.
 
Piet Souris
Master Rancher
Posts: 2042
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For a very readable introduction to regular expressions and all things FSA's, see here:

http://math.hws.edu/FoundationsOfComputation/

especially chapter 3.

Greetings,
Piet
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As an aside, it's quite hard to follow what you write - please get in the habit of using punctuation and capitalization. A forum is not a text message, and you should try to make it easy for people to help you.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!