enter image description here

Hi, what should be the regular expression for this language ? My guess was

r = (a ∗ a(a + b) ∗ (a + b) + (a ∗ b + c))(a + b ∗ ) ∗

But the arrow from C to B is making it tough . If it was B to C then my answer would have bee correct.

  • 3
    $\begingroup$ Don't guess. Make a conjecture and prove it. $\endgroup$ – Yuval Filmus Nov 7 '15 at 12:45
  • $\begingroup$ Once you get to the non-final state $B$ you will never leave, so think about whether you can eliminate $B$ from your automaton. $\endgroup$ – Rick Decker Nov 7 '15 at 18:16

Assuming that the alphabet of your DFA is $\Sigma=\{a,b,c\}$ it doesn't meet the standard definition of the transition function.

$M = \{Q,\Sigma,\delta,q_0,F\}$

$\delta: Q\times \Sigma \rightarrow Q $

If you have a valid DFA then I suggest to use a proved algorithm(like State Removal Method for example) to transform it into a regular expression.


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