I do understand how minimization of DFA works where there are 2 words lets say $\{a, b\}$. However, I came across this minimization of a DFA over the language of $\{a, b, c\}$ $\left(\Sigma, \{q_0, q_1, q_2, q_3, q_4\}, \{(q_0, a, q_1), (q_1, a, q_1), (q_1, b, q_2), (q_2, c, q_3), (q_3, a, q_4), (q_4, a, q_4), (q_4,b,q_2)\}, q_0, \{q_3, q_4\}\right)$

When filling up the table I get some states that brake just because I cannot make a transition from $q_3$ with b. Then if we investigate the set $\{q_4, q_3\}$ in order to see if we can mark it in the table it gives us a broken transition from $q_3$ with $b$ so it looks like $\{q_4, q_3\}$ with $b$ transition $\{q_2, ? \}$ in this case, do we mark $\{q_4, q_3\}$ in the table or not and why?

  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – dkaeae Feb 15 '19 at 13:33
  • $\begingroup$ A DFA should define a transition for each state (i.e., $q_0,q_1,...,q_4$) and each symbol (i.e., $a,b,c$). Are you sure you mean "DFA"? $\endgroup$ – phan801 Feb 15 '19 at 13:40
  • 1
    $\begingroup$ @phan801 The undefined transitions probably trigger an immediate reject response by the DFA (or, alternatively, they land in a "trash" state in which all words are rejected). $\endgroup$ – dkaeae Feb 15 '19 at 13:42
  • $\begingroup$ I wasn't sure when they land in a "trash" state If I have to accept or reject it. It seems that this example is already a Minimised DFA and it was a bit tricky to prove that. $\endgroup$ – Alex Feb 15 '19 at 14:12
  • $\begingroup$ @phan801 This is completely dependant on your definition. I was taught (and always saw in the literature) that DFAs with such missing transitions just reject the word when such a case happens. Moreover, your definition of DFAs is often called a complete DFA. $\endgroup$ – wazdra Feb 15 '19 at 18:27

Your Answer

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

Browse other questions tagged or ask your own question.