hi i am interested in theory of computation. I want to implement the concepts using java...
can anyone give me some sample programs to implement the concepts.... i jus want to implement a software.. can u help me to start it out..
Prithi Samuel
0
Newbie Poster
AuburnMathTutor
37
Junior Poster
Sure.
You know the definition of an NFA, correct? You will need a structure that corresponds as closely as possible to this. In particular, you're going to need the concepts of:
- NFA
- State
- Transition
- Symbol
Java's OOP framework will make it easy to define each of these things in a vacuum. An NFA has a bunch of states, one of which is designated as a start state and some subset of which are accepting states. Transitions go between two (possibly non-unique) states and are activated on either one symbol or no symbol (lambda/epsilon transition).
Now to actually process stuff, you'll want a backtracking (I'd suggest recursive) algorithm that tries each of the relevant transitions at every symbol read. Of course you'll want to save the input because you might need it later... probably best to get the entire string you're testing first. Remember, an NFA accepts if there is any path that accepts, so you'll only need to keep exploring the possibilities until you find a hit.
An alternative is to construct the equivalent DFA from your NFA before testing, but that's more work. The benefit I guess is that if you will be checking lots of strings, this approach is almost guaranteed to be faster.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.