Concept of Regular Language in Theory of Computation

Introduction – About Regular Language

A language is said to be regular if it is accepted by finite automata or has regular expression. In other words, we can say if a particular language is accepted by a machine then the language is said to be regular. A regular language is described by regular grammar.

The concept of a regular language is easy to understand through the pictorial representation mentioned below. Pictorial representation defines how the regular expression, Regular grammar, or finite automata defines the regular language.

Regular Language in TOC

A language is a set of strings that are made up of characters from a specified alphabet, or set of symbols. Regular languages are a subset of the set of all strings. Which are used in parsing and designing programming languages.

These are useful for helping to recognize patterns in data and group certain computational problems together. Regular languages plays important role in computability theory. It can model computational problems which require a very small amount of memory. For example, a finite automaton can generate a regular language to describe if a light switch is on or off, but it cannot keep track of how many times the light was switched on or off.

The machine above can know what state it is currently in, on or off, but it doesn’t know what the history of flips was to get it to where it is (i.e. it doesn’t know how many times the switch has been flipped on or off).

Finite automata generate or model regular languages. This means that regular languages can be described by a simple state machine diagram. A finite state machine, M, describes a given language, L. M is said to accept a string w if the machine starts in a starting state, undergoes a series of state transitions, and ends up in an accepting state. We say that the machine M recognizes the language L if M accepts all strings w that are in L. A language is a regular language if there is a finite automaton that recognizes it. (This will be discussed in detail in some other articles).

Operations on Regular Languages

A regular language can be represented by a string of symbols and operations.

Concatenation

Concatenation is an operation that combines two symbols, sets, or languages. There are two main ways to write a concatenation.  X∘Y and XY both mean “X concatenated with Y.” Languages can also be concatenated: L₁∘L₂ means strings from  L₁ are written first, and then strings from L₂ come after.

Formally, concatenation is defined as follows:  A∘B={xy∣ x ∈ A and y ∈ B}.

Union

Union is an operation where a finite state machine can make one choice or another at any step (this can also be thought of as an “or” operation). For example, there could be a finite state machine that can choose between concatenating XX with YY or concatenating XX with ZZ. Or is written with a vertical bar, and the expression from the previous sentence looks like this: (X∘Y∣X∘Z).

Formally, union is described as follows: A∪B={x∣x∈A or x∈B}. Note, here the vertical bar means “such that.”

Kleene Star

The Kleene star is an operation denoted by an asterisk * that basically represents repeated self-concatenation. For example, if a language LL represents all strings of the form X*, then this language includes X, XX, XXXXXX, XXXXXXXXXXX, etc. The Kleene star can repeat the symbol it operates on any number of times.

The regular language X∘Y∣Z^∗ represents strings of the form “X concatenated with Y or Z repeated any number of times.”

Formally, the Kleene star is defined as follows: A^∗={x₁x₂…x_k ∣ k ≥ 0 and each xi ∈A}. The Kleene star is a unary operation since it operates only on one thing instead of two (unlike union and concatenation, which are binary operations).

Because k can be 0,  x can be repeated 0 times. This means that the empty string is always a member of A^∗.

The Empty String

Another important symbol is ϵ which represents the empty string.

Language Notation

Languages are often written as follows: 

L=(some pattern) ∣∣ (some condition),

where the vertical bar means “such that.” The pattern often resembles something like this 0ⁿ1ⁿ, where the exponent actually represents a unary operation — the 0 would be repeated n times. For example,  0⁴1⁴ is written out as 0000111100001111.