0
$\begingroup$

I am trying find the regular expression that describes the finite automaton 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$
0

2 Answers 2

Reset to default
1
$\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
    Commented Oct 22, 2020 at 16:03
  • 1
    $\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
    Commented Oct 22, 2020 at 16:13
0
$\begingroup$

3rd one will be correct, you can also solve this by minimal sting which is abd and 3rd option is the one that generates abd

Improve this answer
$\endgroup$
1
  • $\begingroup$ (Check sting - not triggering your spelling checker isn't everything.) $\endgroup$
    – greybeard
    Commented Aug 21 at 6:58

Your Answer

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

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