How to prove that a language is regular

We can prove that a language is regular by many various techniques. Several common approaches are listed below.

• Construct a regular expression.
• Design a finite automata.
• Use closure properties.
• Apply the pumping lemma.

Let’s see them in detail now.

1. Construct a regular expression

A string pattern that is recognized by a regular language is defined by a regular expression. It is proof of its regularity if we can create a regular expression that produces the required language.

Example

Let’s suppose language $L$ consists of all strings over the alphabet $\{a, b\}$ that start with an “$a$” and end with a “$b$”.

$$L = \{a, b\} \\ R = a(a+b)b$$

According to this regular expression, the language must begin with a “$a$” ($a$), have zero or more instances of either “$a$” or “$b$” $((a+b))$, and conclude with a “$b$” ($b$).

2. Design a finite automata

Another method to demonstrate regularity is to build a finite automaton, such as a deterministic finite automaton (DFA) or a nondeterministic finite automata (NFA). It gives proof that the language is regular if we can show the automaton can recognize the relevant language.

Example

Let’s suppose language $L$ consists of all strings over the alphabet $\{a, b\}$ that start with an “$a$” and end with a “$b$”.

$$L = \{a, b\}$$

Here is a simple deterministic finite automaton (DFA) for the language $L$.

There are three states for the automaton: $q0$, $q1$, and $q2$. When input “$a$” is given, the starting state, $q0$, changes to $q1$. At state $q1$ if we read “$a$” we will still be at $q1$, but if we read “$b$” we will move to the final state $q2$. At state $q2$ if we read “$b$” we will still be at $q2$, but if we read “$a$” we will loop back to $q1$.

3. Use closure properties

Regular languages are closed under specific operations, and therefore when applied to regular languages, these operations still produce regular languages.

Example

Let’s assume that we have two regular languages, $L1=\{a\}$ and $L2=\{b\}$, respectively. Since $L1$ and $L2$ only have one character per word, they are both regular languages. Now that we have the language $L = L1.L2,$ which represents strings that start with an “$a$” and end with a “$b$”. Since the concatenation of regular languages results in a regular language, $L$ is also regular.

4. Apply the pumping lemma

The pumping lemma for regular languages is a useful tool for proving that a language is not regular. It may also be used to demonstrate that a language is regular by proving that it meets the pumping lemma requirements. If the pumping lemma is correctly applied and its conditions are met, it provides evidence that the language is regular.

If you want to see how the pumping lemma works you can refer to the following link.