Im seeking clarification and a rigorous proof regarding the equivalence of r^n and r^{..n} in the context of formal languages, particularly when r is nullable.

To clarify the terminology:

  • r denotes the regular expression
  • r^n denotes exactly n repetitions of r.
  • r^{..n} represents any number of repetitions of r, from zero to n.

I've come across a statement suggesting that when r is nullable (able to produce an empty string), r^n is equivalent (equals) to r^{..n}.

This concept makes sense to me intuitively, but I'm looking for a more formal proof or example to solidify my understanding.

Could someone provide a clear and formal proof, or perhaps an illustrative example, that demonstrates why r^n is indeed equivalent to r^{..n} when r is nullable?

I appreciate any insights and guidance on this matter.

  • $\begingroup$ This is not a research-level question, but a rather trivial consequence of the definition. You should take the question to cs.stackexchange.com , not here. $\endgroup$ Oct 15, 2023 at 16:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.