The true power of regular expressions

The true power of regular expressions.

What does “regular” actually mean?

In the context of formal language theory, something is called “regular” when it has a grammar where all production rules have one of the following forms:

B -> a
B -> aC
B -> ε
You can read those -> rules as “The left hand side can be replaced with the right hand side”. So the first rule would be “B can be replaced with a”, the second one “B can be replaced with aC” and the third one “B can be replaced with the empty string” (ε is the symbol for the empty string).

So what are B, C and a? By convention, uppercase characters denote so called “non-terminals” - symbols which can be broken down further - and lowercase characters denote “terminals” - symbols which cannot be broken down any further.