3
$\begingroup$

Here is a finite state machine which can be recognised with a regular language. enter image description here

The regular expression which I've got for this FSM is:

(10(0+(10))*11+11+00*10(0+(10))*11+00*11)(0+1)*

Is this correct? If so how do I keep simplifying the expression further with no term disappering? For example if I want to factorise 11 from the expression within the grater paranthesis, the second term will then dissapear.

$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Preliminary remark. The sentence "Here is a finite state machine which can be recognised with a regular language" does not make real sense. It should be: "Here is a regular language recognised by the following finite state machine".

Your regular expression is correct but can be simplified. To do so, first minimise your deterministic automaton. Using the standard minimisation algorithm, you will find the following equivalences among the states: $s_0 \sim s_1 \sim s_3$ and $s_2 \sim s_5$. Thus, if I am not wrong, your automaton is equivalent to this one

$\hskip 100pt$

which leads to the simplified regular expression $(0 + 10)^*11(0+1)^*$.

$\endgroup$

You must log in to answer this question.

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