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

The Agile Manifesto in Practice: Part 1

The Agile Manifesto in Practice: Part 1

  How Sourcetoad Values People Over Process The software development process can involve a lot of uncertainty for both development teams and clients alike, especially in the early phases of a project. How can the long-term vision of an application be balanced...

What to Consider When Building HIPAA-Compliant Software

What to Consider When Building HIPAA-Compliant Software

In 1999, the Department of Health and Human Services (HHS) passed the Health Insurance Portability and Accountability Act (HIPAA) as a measure to protect personal health information (PHI) and allow people control of their healthcare records. The HITECH Act was enacted...

The Evolution of Buy Now, Pay Later in eCommerce: Part 2

The Evolution of Buy Now, Pay Later in eCommerce: Part 2

In Part 1, we talked about the rapid growth of Buy Now, Pay Later (BNPL) and discussed its expansion across industries. In Part 2, we will consider how impending regulation may shake up the short-term lending space.   Impending Regulation of BNPL While consumers...