1
$\begingroup$

I'm having some trouble to design a DFA that accepts the language defined by this regular expression

$(a + b(ba)^*)^*b$

Can I say that $(a + b(ba)^*)^*$ is the same as $(a + b)^*$ ? Given this assumption, here is my DFA ("all strings over $\{a, b, \epsilon\}$ ending in $b$"):

enter image description here

Thanks in advance!

$\endgroup$

1 Answer 1

1
$\begingroup$

Your statement that $(a + b(ba)^*)^*$ is the same as $(a + b)^*$ is correct. Your DFA is correct, but is not minimal: you could identify states $q_1$ and $q_2$.

$\endgroup$
1
  • $\begingroup$ You're welcome. $\endgroup$
    – J.-E. Pin
    Apr 29, 2018 at 22:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .