Properties of regular languages

• $L_1 = \{ \text{All strings that end with a } b \}$
• $L_2 = \{ \text{All strings that contain } bab \text{ as the substring} \}$
• $L_3 = \{ \text{All strings of even length} \}$
• $L_4 = \{ \text{All strings having a length not more than } 10 \}$

In this blog, we discuss the closure properties of regular languages and pumping lemma.

Regular languages are closed under many set-theoretic operations including reversal, concatenation, Kleene closure, complement, union, and intersection. Let’s discuss and prove why regular languages are closed under all these properties.

Regular languages are closed under the reversal operation. The reverse of a string, $w$, is notated as $w^R$. If $w \in L$, then $w^R \in L^R$. If $L$ is a regular language, then there exists an NFA to recognize $L$. An NFA can be constructed to recognize $L^R$ if an NFA for $L$ is given using the following procedure:

1. Create a new state and add $\epsilon$-transitions from the final states of the NFA to the new state.
2. Make the existing final states nonfinal.
3. Make the existing start state of the NFA the final state of the new NFA.
4. Make the newly added state the start state of the NFA being constructed.
5. Finally, invert the direction of all the transitions.

The NFA that recognizes $L$ is shown below:

The resultant NFA that recognizes $L^R$ is shown below.

Regular languages are closed under the concatenation operation. If two languages are regular then there exist two NFAs to recognize these languages. We create a new NFA having $\epsilon$-transition(s) from the final state(s) of the first NFA to the start state of the second NFA and remove the final status of all final states of the first NFA. The initial state of the second NFA will no longer be the initial state of the resultant NFA. The resultant NFA recognizes the concatenation of two given languages whose NFAs have been used to construct the new NFA.

Regular languages are closed under Kleene closures. The Kleene closure of a language (or a set) is defined as follows:

$$L^* = \bigcup_{i\geq0}L^i=L^0 \cup L^1\cup L^2 \cup L^3\cup ...$$

Here,

$$L^0={\epsilon}$$

and

$$L^1=L$$

$L^i$ is recursively defined as follows:

$$L^i=\{uw:u \in L^{i-1} \text{ and }w \in L\} \text{ for }i\geq2$$

The following figure presents a DFA for a regular language $L$:

Its Kleene closure ($L^*$) is computed by the construction of the NFA, as follows:

• Add $\epsilon$-transition(s) from the start state to the final state(s).
• Add $\epsilon$-transition(s) from the final state(s) to the start state.

Regular languages are closed under the complement operation. If a language is regular, then there exists a DFA to recognize it. All strings whose consumption ends up in a final state are part of the language. And all strings whose consumption ends up in a nonfinal state are part of the complement of the language. So, to construct a DFA for the complement, all final states are made nonfinal and vice versa. The resulting DFA recognizes the complement of the language. The following figure represents a DFA recognizing a regular language.

The following figure presents the DFA that recognizes the complement of the given language.

Regular languages are closed under the union operation. If two languages are regular then there exist two NFAs to recognize these languages. We create a new NFA having $\epsilon$-transitions from its start state to the start states of the given NFAs. The resultant NFA recognizes the union of two given languages whose NFAs have been used to construct the new NFA.

Regular languages are closed under the intersection operation. The intersection of two languages (or sets) is defined as follows using DeMorgan’s law:

$$L_1 \cap L_2 = \overline{\overline{L_1}\cup \overline{L_2}}$$

Let’s deconstruct the expression above:

• If $L_1$ and $L_2$ are regular languages, then $\overline{L_1}$ and $\overline{L_2}$ are regular because regular languages are closed under the complement operation.
• If $\overline{L_1}$ and $\overline{L_2}$ are regular, then $\overline{L_1} \cup \overline{L_2}$ is regular because regular languages are closed under the union operation.
• If $\overline{L_1} \cup \overline{L_2}$ is regular, then $\overline{\overline{L_1}\cup \overline{L_2}}$ is regular because regular languages are closed under the complement operation.
• If $\overline{\overline{L_1}\cup \overline{L_2}}$ is regular, then $L_1 \cap L_2$ is regular because they are equal according to DeMorgan’s law.

Pumping lemma is an important and interesting property of regular languages.

If a language is regular, then there exists a DFA that recognizes the language. Let’s notate the number of states of the DFA as $m$ where $m$ is a finite positive integer.

For an infinite regular language $L$, the DFA must contain at least one nonempty loop. If $w \in L$ and $|w| \geq m$, then $w$ can be written as follows:

$$w = xyz$$

such that $|xy| \leq m$ and $|y| \geq 1$. Because $|w| \geq m$ and $w \in L$, there must exist a walk from the start state to one of the final states of the DFA to consume $w$. The number of states in the DFA is $m$. So the longest walk without repeating a state can be of $m-1$ length. To consume $w$, at least one of the states must be repeated, otherwise $w$ can’t be accepted. The repeating part of the walk makes the substring $y$. The part of the string before the repeated part makes the substring $x$, and the part of the string after the repeated part makes the substring $z$. The following figure shows a breakdown of the substrings that make up a valid string $w$ to be accepted by the DFA:

The pumping lemma states that if $w=xyz$ and $w \in L$, then $wy^iz \in L, \forall i \geq 0$. It implies that if a walk from the start state to the final state is decomposed into three substrings, then there are two types of behaviors being observed: repeating parts of the walk and nonrepeating parts of the walk. Here, $y$ is the repeating part. If $y$ repeats itself $i$ times then the resulting walk from the start state to the final state remains part of the language. Therefore, all forms of the walk, where $y$ is repeating $i \geq 0$ times are part of the language. For instance, $xz$, $xyz$, $xyyz$, $xyyyz$, and so on, will be part of the language.

A regular language can be proved to be regular using different methods including:

• Construct a DFA or NFA
• Write a regular expression
• Use closure properties
• Use an appropriate logical combination of these methods

For example, let’s prove that the following language is regular:

$$L=\{ w: w \in \{ a, b \}^* \text{ and the length of } w \text{ is not a multiple of 3} \}$$

One way to prove that $L$ is regular is as follows:

• Construct a DFA for the language $L'$ defined as:

$$L'=\{ w: w \in \{ a, b \}^* \text{ and length of } w \text{ is a multiple of 3} \}$$

• $L'$ is regular because it has a DFA that recognizes it. We know that regular languages are closed under the complement operations. Therefore, $\overline{L'}=L$ is also regular.

Let’s understand this through two examples:

Our task is to prove that the following language is not regular:

$$L_5=\{a^nb^n:n \geq 0 \}$$

As $n \geq 0$, therefore, $L_5$ is infinite. Assume that $L_5$ is regular. If it is regular then there exists a DFA that recognizes $L_5$. The number of states in the (assumed) DFA will be a finite integer, say $m$.

Let’s choose a string $w \in L_5$, such that $|w| \geq m$.

$$w=a^mb^m$$

Here, $|w|=2m \geq m$. The chosen string $w$ can be decomposed into three substrings $x$, $y$, and $z$ such that $|xy| \leq m$ and $|y| \geq 1$. Let’s represent the length of $y$ as $k$, where $1 \leq k \leq m$. In this string, $x$ and $y$ both have to fall within $a'$s because their combined length can’t go beyond $m$. Let’s repeat $y$ twice and create a new string $w'$.

$$w'=xy^2z=xyyz$$

$$|w'|=|w|+|y|=m+k$$

Because $y$ is a composition of $k$ number of $a'$s, the resulting string will be:

$$w' = a^{m+k}b^m \notin L_5$$

According to the pumping lemma, $w' \in L_5$, but we 've demonstrated that $w' \notin L_5$. Therefore, our assumption is incorrect and the given language is not regular.

Our task is to prove that the following language is not regular:

$$L_6=\{a^n:n \geq 0 \text{ and } n \text{ is a perfect square} \}$$

Because $n \geq 0$, therefore, $L_6$ is infinite. Assume that $L_6$ is regular. If it’s regular, then there exists a DFA that recognizes $L_6$. The number of states in the (assumed) DFA will be a finite integer, say $m$.

Let’s choose a string $w \in L_6$, such that $|w| \geq m$.

$$w=a^{m^2}$$

Here, $|w|=m^2 \geq m$. The chosen string $w$ can be decomposed into three substrings, $x$, $y$, and $z$, such that $|xy| \leq m$ and $|y| \geq 1$. Let’s represent the length of $y$ as $k$ where $1 \leq k \leq m$. In this string, $x$ and $y$ both have to fall within the first $m$ number of $a$'s because their combined length can’t go beyond $m$. Let’s repeat $y$ twice and create a new string $w'$.

$$w'=xy^iz=xyyz$$

$$|w'|=|w|+|y|=m^2+k \leq m^2 + m$$

The lower limit on the length of the new string $w'$ is $m^2 + 1$. The upper limit on the length of the new string $w'$ is $m^2+m$.

$$m^2 + m < m^2+2m+1 = (m+1)^2$$

Even the upper bound of $|w'|$ falls below the next perfect square, i.e. $(m+1)^2$.

According to the pumping lemma, $w' \in L_6$, but we’ve demonstrated that $w' \notin L_6$. Therefore, our assumption is incorrect and the given language is not regular.

For an in-depth understanding of different classes of computational problems and their characterization, you can explore the following course: