An In-Depth Look at Regular Expressions Part 2: Regular Languages

Jun 21, 2016

So we’ve discussed what a language is from a computer science theory viewpoint in part 1 of this series, and we have 2 ways of representing languages:
Set notation: {λ, a, aa, aaa, ...} or {a^n | 0 <= n} for short,
and grammar production rules: {S -> aS | λ}

As I stated in part 1, a regular expression is a representation of not just any language, but a regular language specifically.

Regular languages are just languages with certain restrictions. To avoid getting too confusing and mathy, we’re going to skip over the formal definition of a regular language and jump straight to regular grammars; recall that a grammar is simply a way of representing a language, so a regular (or linear) grammar is a representation of a regular language (just like a regular expression!). So one example of a regular grammar is one in which every production rule is of the form: A -> aB, A -> a, or A -> λ, where A and B are non-terminals, and a is a terminal (this is called a left linear or left regular grammar).

For example:

P = {
S -> aB
B -> bC
C -> c
}

Each production rule in this grammar fits one of the forms above, so it is a regular grammar, and therefore the language represented by this grammar is a regular language.
Note: There are other grammars that represent this same language, such as:

P1 = {
S -> abc
}

or

P2 = {
S -> Bc
B -> Ab
A -> a
}

(For the record, P2 is an example of a right linear grammar)

Depending on the language or library you’re using, regular expressions have a lot of extra features and shortcuts, but a standard regex has only 3 basic operations:
1) Concatination (ab)
2) Alternation (a|b)
3) Kleene Star (a*)

Any other operation can be made from these operations.
The + operator, for example, can be defined as: a+ is equivalent to a(a*)
Another useful operator is the ? operator, which can be defined as: a? is equivalent to (a|)

RECENT POSTS

Meet Sourcetoad, a 2023 Best Places to Work honoree

Meet Sourcetoad, a 2023 Best Places to Work honoree

Tampa Bay Business Journal — April 26, 2023 Sourcetoad has been selected as a 2023 Best Places to Work! We are thrilled to be among Tampa's top workplaces for the fourth year in a row, and we are grateful to each of our Toads for making Sourcetoad such a fantastic...

This Year in FinTech: Trends to Watch in 2023

This Year in FinTech: Trends to Watch in 2023

The financial services industry experienced rapid digitization throughout the COVID-19 pandemic, and growth of the financial technology market is expected to continue in 2023. The global fintech market grew to $158.9 billion in 2022, and projections estimate it will...

2023 Top HealthTech Trends

2023 Top HealthTech Trends

Technological innovation has played a vital role in the transformation and growth of the healthcare industry. Not only is the medical space an early adopter of emerging technologies, HealthTech is currently one of the fastest-growing industries worldwide. The global...