From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$.

So the Automata in the picture is not equivalent to the RE?

  • 2
    $\begingroup$ $(L|D)^+ \equiv (L|D)(L|D)^\ast$, hence after a word in $\_(L|D)$ there can be arbitrary many words matching $(L|D)$. $\endgroup$ – ttnick Mar 17 '20 at 8:09
  • $\begingroup$ @ttnick: Thank you! $\endgroup$ – Ning Mar 17 '20 at 8:11
  • 3
    $\begingroup$ @ttnick answers in answers, not comments, please $\endgroup$ – D. Ben Knoble Mar 17 '20 at 13:38

They aren't equivalent. For example, the string "L__L" is described by the expression, but not accepted by the automaton (no way to have two '_' in a row).

  • $\begingroup$ The expression does not allow two consecutive "_". Perhaps you misread a plus as a kleene star? $\endgroup$ – frabala Mar 18 '20 at 16:18

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.