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$ 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$ 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$ Commented Aug 21, 2024 at 6:58

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.