0
$\begingroup$

I am trying find the regular expression that describes the finite automata in the image below.

Given the following finite automata Finite Automata

which of the following regular expressions describes the same language as the automaton.

  • (ab)+c*d+
  • a+b+c*d+
  • a(ba)*bc*dd*
  • [ab]+c*d+
  • a(ba)*bc+d?d+
  • (ab)+c+d*

I tried converting it to a regular expression and I got (ab)*ac*dd*, which is not among any of the options. Could someone help me select the correct answers?

Improve this question
$\endgroup$
1
  • $\begingroup$ I got (ab)*ac*dd* how did you get the a between b and d? (dd* is fine, depending on context/definition, d+ is a shorter version thereof.) $\endgroup$
    – greybeard
    Oct 22, 2020 at 16:20

1 Answer 1

Reset to default
0
$\begingroup$

You have an error in your regular expression. The correct one is $(ab)^*ab c^*dd^*$ (notice that after reading $(ab)^*$ you are in state $A$ and that the edge from $B$ to $C$ is labelled $b$).

This can be rewritten as $(ab)^+ c^*d^+$ since $(ab)^*ab = (ab)^+$ and $dd^* = d^+$.

Another equivalent expressions is $a(ba)^*bc^*dd^*$ since $(ab)^+ = a(ba)^*b$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your help. Do you know any website where I can learn the equations you used to rewrite the expression? $\endgroup$
    – Dappa jack
    Oct 22, 2020 at 16:03
  • $\begingroup$ No, sorry. What I used is just the definition of "plus". If $E$ is a regular expression then $E^+$ is defined as $EE^*$ (or equivalently $E^*E$). The equality $(ab)^+ = a(ba)^*b$ follows from the fact that both expression correspond to words with $k \in {2,4,6,\dots}$ alternations of "a" and "b". Therefore $(ab)^+ = ab(ab)^* = (ab)^*ab = a(ba)^*b$. $\endgroup$
    – Steven
    Oct 22, 2020 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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