0
$\begingroup$

If we have a regular expression $R$, will $R$ describe only regular language $L$, but that language $L$ can have multiple different regular expressions such as $Q,W,A,S,D \ etc..$ describing it

Also, $R$ can be equivalent, in terms of describing $L$, to infinite regular expressions including $ Q,W,A,S,D \ etec..$

Is my understanding correct?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ How could a regular expression describe more than one language? $\endgroup$
    – Criticizing Israel not allowed
    Commented Jan 10, 2023 at 9:45

1 Answer 1

Reset to default
0
$\begingroup$

If $e$ is a regular expression such that $\mathcal{L}(e) = L$, then so is $e+\emptyset$, $e+\emptyset+\emptyset$, …

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes!! One more doubt regarding what you said ~ it's also possible to have two completely different regular expressions describing a regular language correct? Asking because different methods like arden's or state elimination method produce different expressions. Even in Arden's theorem, sometimes the order in which we substitute leads to different expressions. According to me, it's possible $\endgroup$
    – Pratik Hadawale
    Commented Jan 10, 2023 at 12:20
  • $\begingroup$ "it's also possible to have two completely different regular expressions describing a regular language correct?" > that's litteraly what my answer prove. $\endgroup$
    – Nathaniel
    Commented Jan 10, 2023 at 12:26
  • $\begingroup$ Oh my bad, i thought your gave an example for the "a regular expression is equal to inifinite other regular expressions". Thank You! and sorry for misunderstanding $\endgroup$
    – Pratik Hadawale
    Commented Jan 10, 2023 at 12:27
  • $\begingroup$ A regular expression is a sequence of symbols. Two regular expressions with different sequences of symbols cannot be equal. However, the language they describe can be equal. That's why I am talking about the interpretation of a regular expression, denoted $\mathcal{L}(e)$. Though one can sometimes write something like $(a+b)^* = (a^*b^*)^*$, this is an abuse of notation that, in reality, means $\mathcal{L}((a+b)^*) = \mathcal{L}((a^*b^*)^*)$. $\endgroup$
    – Nathaniel
    Commented Jan 10, 2023 at 12:49

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.