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 Evolution of Buy Now, Pay Later in eCommerce: Part 1

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

If you’ve shopped online recently, you’ve probably noticed an increase in financing options being offered at checkout. An increasingly popular option, “Buy Now, Pay Later” (BNPL) services offer instant short-term loans at point-of-sale (POS), often without interest or...

The State of Mobile Apps in the Cruise Industry

The State of Mobile Apps in the Cruise Industry

Since 2018, Sourcetoad has been very interested in the world of cruise mobile applications and their features. We’re interested partly because we want to be better software engineers, and partly so that we can better inform our clients. This interest drove us to begin...