Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
