0
$\begingroup$

Let's say that we have a DFA, where the initial state was also the accept state. Meaning the DFA accepts the "empty string". Now, let's say that we convert the DFA to regular expression $R$, using Arden's Method ( my prefered method )

Now, the resultant expression looks something like $(R)^*$, which is obviously capable of representing empty string, implying that the language we are describing also accepts empty string. But is it legal to represent empty string as a "kleene star" or do i have to explicitly mention "empty string" + $R$

My understanding is that, it's okay to represent it as Kleene star

$\endgroup$
1
  • $\begingroup$ Nothing in a regular expression explains "how" a sentence matches. It only says which sentences match. A match is a match. If the regular expression produces the correct set of sentences, it is correct. $\endgroup$
    – rici
    Jan 10, 2023 at 14:08

1 Answer 1

1
$\begingroup$

If the start state is also a final state, then the empty word must be in the interpretation of the regular expression you obtain.

That does not necessarily mean that the regular expression $e$ you obtain is of the form $E = F^*$, for example, the interpretation of $(a+b)^*aab(a+b)^*\mid (ba)^*$ contains the empty word.

However, if that's not the case, then that means you made a mistake somewhere, no matter the method.

I am not so sure what you mean by 'is it legal to represent empty string as a "kleene star"': if the interpretation of $F$ is not the empty language, then $F^*$ does not represent only the empty word. However, $\emptyset^*$ contains only the empty word.

$\endgroup$
1
  • $\begingroup$ Given that the start state is also a final state, i tend to get equations like : $( \ b + ab^*a \ )^*, ( \ a + b(b+ab)^*aa \ )^*$ What I meant by legal is, see the original DFAs accepted empty string and here i don't have an explicit "empty string symbol" but "the outermost kleene star operation is capable of producing the empty string with other strings, so is that okay? Looks like it is from your answer $\endgroup$ Jan 10, 2023 at 12:12

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.