How to check correctness of finite state automata we have designed for a regular expression with the help of any computer program or prolog?
Asked
Active
Viewed 148 times
1
-
You can check it manually only if it is a small automaton. Try to find a string accepted by automaton but should not be word of the language. – user110219 Oct 08 '14 at 11:31
-
There is an algorithm for converting regular expressions to finite state automata. Isn't this enough? – Ayman Hourieh Oct 08 '14 at 11:32
-
Ayman, could you please tell me more about that algorithm? – Madhusudana Oct 08 '14 at 12:09
1 Answers
1
You can follow the following steps. Each step is meant to be realized by an algorithm, not manually:
- Convert the regular expression to a NFA.
- Convert the NFA to an equivalent DFA.
- If the FSA that you have defined is a NFA, convert it to an equivalent DFA.
- Test the two DFAs for equivalence.
Edit: There is an online implementation of the first two steps here.
For step 4 you can look at slides 2-7 here.
posilon
- 2,253