Converting Nondeterministic finite automata(NFA) to deterministic finite automata(DFA)
-
-
Hi, I have to write a program which converts NFA to DFA.I know the algorithm, but I have no idea, how translate it to any C++ / Java code. I would be grateful for advices how to do it (simple pseudocode or something), Thank you for any sugestion Paul
I'm puzzled here, you say you know the algorithm, so you have or could write an English description of it; well, that is the pseudo-code you want, isn't it? I think what you need most is the courage the get started... :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
-
Hi, I have to write a program which converts NFA to DFA.I know the algorithm, but I have no idea, how translate it to any C++ / Java code. I would be grateful for advices how to do it (simple pseudocode or something), Thank you for any sugestion Paul
Define the DFA "state" of an NDFA as being the list of all states that the NDFA "could" be. Then determine for each possible combination of states, what combinations of states could occur as a result of each possible input character. For example, consider the following NDFA: 1. START STATE. If input is "T", maybe advance to state 2. In any case, maybe stay in state 1. 2. If input is "E", advance to state 3. 3. If input is "S", advance to state 4. 4. If input is "T", advance to state 5. 5. If input is "E", advance to state 6. 6. If input is "R", advance to state 7. 7. ACCEPTING STATE. Stay in state 7 regardless of input. It's possible that the machine will only be in state 1 (call that DFA state "1"). If it's in DFA state 1 and it gets a "T", it could be in state 1 or 2 (call that DFA state "1/2"); if it gets anything else, it can only be in state 1. If it's in DFA state "1/2" and it gets a "T", it could be in state 1 or 2; if it gets an "E", it can be in state 1 or 3 ("1/3"). Anything else, it can only be state 1. If it's in DFA state "1/3" and it gets a "T", it could be in state 1 or 2; if it gets an "S", it can be in state 1 or 4 ("1/4"). Anything else, it can only be state 1. If it's in DFA state "1/4" and it gets a "T", it could be in state 1, 2, or 5. Anything else, it can only be state 1. If it's in DFA state "1/2/5" and it gets an "E", it could be in state 1, 3, or 6. Anything else, it can only be state 1. If it's in DFA state "1/3/6" and it gets an "R", it could be in state 1 or 7 (though state 1 won't really matter); if "S", it can be in state 1 or 4; if "T", state 1 or 2. Anything else, it can only be state 1. If it's in DFA state "1/7", one could evaluate further state transitions, but since "acceptance" is guaranteed, they're moot.
-
I'm puzzled here, you say you know the algorithm, so you have or could write an English description of it; well, that is the pseudo-code you want, isn't it? I think what you need most is the courage the get started... :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
-
Hi, Because I'm not fluent in English I'm giving link to little drawing shows converting ;) http://www.mojalbum.com.pl/Zdjecie-OESVBLB4-D.jpg[^] Writing "pseudocode" a mean something closer to any programming language.
the image only shows an example of input and output. it is not an algorithm. if you know the algorithm, it is expressed either in human language or in a programming language, the former is easier for humans (and possibly ambiguous), the latter is easier for machines. If you don't have the algorithm, come up with one yourself and/or do your research through google. There's lots of relevant stuff around. Maybe this CP article is useful: Writing own regular expression parser[^] :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
-
Hi, Because I'm not fluent in English I'm giving link to little drawing shows converting ;) http://www.mojalbum.com.pl/Zdjecie-OESVBLB4-D.jpg[^] Writing "pseudocode" a mean something closer to any programming language.
-
Paul6915 wrote:
is very stupid, but works
A program can be very stupid, or it can work. It can't do both. If you've written a program that solves the problem, you have every reason to be proud of it. When someone comes up with a better program to solve the same problem, you have a learning opportunity.
"A Journey of a Thousand Rest Stops Begins with a Single Movement"
