Explore BrainMass

Theory of Computation : Non-deterministic finite state automaton

Give a non-deterministic finite state automaton that recognizes the language L subset {0,1}* that consists of all words w such that some appearance of two 0's in w is separated by an even number of 1's. (For example: the words 0010010110, 001101 are in the language but the words 0101110, 001001 are not.)

(As a note, this is the exact problem I have been asked, and can only assume that the examples of words accepted and not accepted that has been given contains a mistake, since the difference cannot be detected between the word 0010010110, and the word 001001. Ignoring the examples, is it possible to construct an accurate NFA from how it is described? I assume "some appearance" to mean all appearances for the purpose of constructing the automata.)

Then use the subset construction to convert the obtained NFA into a deterministic finite state automaton.

Please see the attached file for the complete problem description. Also, I have included copies for reference of:

1) The theorem stating the equivalence of NFA's and DFA's:
Theorem: Every nondeterministic finite automaton has an equivalent deterministic finite automaton.
2) The previous theorem's proof.
3) An example in the book, illustrating the procedure given in the above proof for converting a given NFA into a DFA.
4) An example showing the exact steps to be completed in converting a given NFA into a DFA.

I included these to help make the problem easier, and to be sure that what is being asked in this problem makes sense to everyone who reads it.


Solution Preview

If I got time tomorrow, I would definitely help you figure out the DFA part. Today I really do not have enough time.

Here enclosed is the NFA. I tested on the following two ...

Solution Summary

A non-deterministic finite state automaton is investigated.