0
$\begingroup$

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

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*"

Improve this question
$\endgroup$
3
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics. See here for a short introduction. Using * in text environment is interpreted as italic. $\endgroup$
    – Nathaniel
    Commented Dec 28, 2022 at 16:33
  • $\begingroup$ @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? $\endgroup$
    – Arun Madhav
    Commented Dec 29, 2022 at 3:50
  • $\begingroup$ Yes, the left most automaton is an "epsilon NFA" and rest are NFAs without epsilons and yes you are correct! $\endgroup$
    – Pratik Hadawale
    Commented Dec 29, 2022 at 5:12

3 Answers 3

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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" $\endgroup$
    – Pratik Hadawale
    Commented Dec 29, 2022 at 5:16
  • $\begingroup$ @PratikHadawale This is incorrect. aabbcc belongs to abc* but doesnt belong to either of the previous ones. $\endgroup$
    – whoisit
    Commented Dec 29, 2022 at 8:15
  • $\begingroup$ @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. $\endgroup$
    – Arun Madhav
    Commented Dec 29, 2022 at 8:22
0
$\begingroup$

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 $

Improve this answer
$\endgroup$
0
$\begingroup$ 
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*
Improve this answer
$\endgroup$

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.