given 'r' , a regular expression that does not include λ or ∅, What are the Conditions of 'r' so that L(r) would be infinite?


1 Answer 1


Regular expressions correspond to a simple recursive definition, which starts with the symbols from some alphabet and extends them with applications of three operators: alternation, concatenation and Kleene closure.

So ask yourself: Which of these operators can produce an infinite set?

Formal definition:

Let $\Sigma$ be a finite set of symbols. Then the set of regular expressions $R_\Sigma$ is the smallest set of expressions which can be constructed using these rules:

  • Every $c \in \Sigma$ is in $R_\Sigma$.

  • $\lambda$ and $\emptyset$ are in $R_\Sigma$.

  • If $r$ and $s$ are regular expressions over the alphabet $\Sigma$ then so are:

    • $(r+s)$
    • $(rs)$
    • $(r^*)$

A standard proof technique for properties of regular expressions is to apply mathematical induction to this definition.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.