Finite and Infinite Regular Expressions

 

🟢 Finite Regular Expressions

A finite regular expression defines a language that contains a finite number of strings.

✅ Characteristics:

• The set of strings it describes is limited in size.

• There are no operators like Kleene star (*) used in a way that can generate infinite strings.

🔹 Examples:

1. a

   • Language: {a} → contains only one string

2. ab + ba

   • Language: {ab, ba} → two strings

3. (a + b)(a + b)

   • Language: {aa, ab, ba, bb} → exactly 4 strings

🧠 Note:

Any regular expression without the Kleene star (*) or plus (+) used repetitively will usually define a finite language.

---

🔁 Infinite Regular Expressions

An infinite regular expression defines a language that contains an infinite number of strings.

✅ Characteristics:

• These expressions use Kleene star (*) or Kleene plus (+) which allows repetition zero or more times, or one or more times.

• The number of strings in the language is unbounded.

🔹 Examples:

1. a*

   • Language: {ε, a, aa, aaa, aaaa, ...} → infinite

2. (ab)*

   • Language: {ε, ab, abab, ababab, ...} → infinite

3. (a + b)*

   • Language: All strings over {a, b} including ε → infinite