0
$\begingroup$

How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius}

I came with this solution:

>(0)--p-->(1)--u-->(2)--s-->(3)--t-->(4)--a-->(5)--i-->(6)(goto state 0)
  |
 (7)--m-->(8)--a-->(9)--r-->(10)--i-->(11)--u-->(12)--s-->((13)) (final state)

How can I know if this is implemented correctly? And about minimization of this automate I think is impossible.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ This is not a DFA since it seems one can go from state 0 to state 7 without any input, though it is close to a DFA. Also, it repeats your last name an arbitrary number of times (including zero), before going to your fist name. It does not correspond to your definition of L. $\endgroup$ – babou Jun 30 '14 at 12:24
2
$\begingroup$

Write down all accepting paths, that is paths from the starting state to final states. These are all the words the given automaton can accept; if the set is the desired one, q.e.d.

This is only possible and a rigorous proof for (co-)finite languages. Once you have cycles you have to apply induction. See here for an in-depth explanation on how to do this for grammars; it's similar for automata.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.