Regular Expression for a infinite language

Question

I'm just kind of confused about regular expressions. Can there be a regular expression that recognizes an infinite language or do all regular expressions recognize finite languages?

Answer 1

It is definitely possible to build regular expressions that recognize infinite languages. For example, the simple regular expression a* matches the infinite language

{ ε, a, aa, aaa, aaaa, ... }

The star operator is essential in regular expressions to enable them to recognize infinite sets of strings.

It is true that all finite languages are regular, but not all regular languages are finite (as shown above). Formal language theory tells us that there are a lot of languages that are infinite but not regular (such as {0ⁿ1ⁿ | n ≥ 0}), though, so you can't always write a regular expression for an arbitrary infinite langugage.

Hope this helps!