# Can we further minimize this regular expression: a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*

I am trying to create the regular expression for the automaton named "full closure" in the following diagram using the arden's theorem:

Since, we have 3 accepting states, we would find 3 different regular expression and then just union them up. I was able to find regular expression for q0, q1 but facing issues when trying to find one for q2:

q0 = a*
q1 = a*b* + b*
q2 = a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*

EDIT: I was able to minimize the final expression that is r = q0 + q1 + q2, to

r = a*b*c* + a*bc* + b*c*

can we further minimize this expression to "a*b*c*"?


My question is can we further minimize this regular expression for q2 and overall when we union? The "full closure" automata recognizes language "a* b* c*"

• Note that you can use LaTeX here to typeset mathematics. See here for a short introduction. Using * in text environment is interpreted as italic. Commented Dec 28, 2022 at 16:33
• @Partik Hadawale why are there 3 horizontal arrows pointing at each state in full closure and forward closure? does that mean we can start our automata from any of these states? Commented Dec 29, 2022 at 3:50
• Yes, the left most automaton is an "epsilon NFA" and rest are NFAs without epsilons and yes you are correct! Commented Dec 29, 2022 at 5:12

As $$a^{*}bc^{*}$$ and $$b^{*}c^{*}$$ are subsets of $$a^{*}b^{*}c^{*}$$ we can write the regular expression as $$a^{*}b^{*}c^{*}$$.

• do we just state this as the most logical thing to do? or is there an identity for it? Like a* b c* says "we need exactly 1 b" whereas b* c* says "we can have 0 bs and no as" Commented Dec 29, 2022 at 5:16
• @PratikHadawale This is incorrect. aabbcc belongs to abc* but doesnt belong to either of the previous ones. Commented Dec 29, 2022 at 8:15
• @PratikHadawale I don't know of any identity for minimizing regular expression, so it would be the most logical thing to do as $r$ is the union of $a^{*}b^{*}c^{*}$ and subsets of $a^{*}b^{*}c^{*}$ hence we don't need to consider the subsets but in the case $a^{*}bc^{*}$ and $b^{*}c^{*}$ neither of them is a subset of the other hence we need to consider both of them. Commented Dec 29, 2022 at 8:22

Obviously yes because every single string ends in c*.

Note that (x)*y is always a superset of y, so if both are present then y can be removed. We do this and get

$$a^*(ac^* + b^*bc^* + b^*cc^* ) + c^*$$

$$b^*cc^*$$ includes $$c^*$$ except $$\epsilon$$, so this is $$a^* (a + b^*b + b^*c) c^* + \epsilon = a^* (a + b^*(b + c)) c^* + \epsilon$$

a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c* =
(a*a + a*b + a*c + a*b*b + a*b*c + b*b + b*c + ϵ)c* =
(a*a + a*b*b + a*b*c + ϵ)c* =
a*(a + b*b + b*c + ϵ)c*