4
Consider the following languages:
$L_1=\{a^{2^z}\mid z\text{ is an integer}\}$
$L_2=\{a^{2z}\mid z\ge 0\}$
$L_3=\{\omega\omega\mid \omega\in\{a,b\}^*\}$
Which of the languages is or are regular?
Choose the correct answer from the options given below:
Solution
For $L_1$:
$L_1=\{a^{2^z}\mid z\text{ is an integer}\}$
The possible lengths are:
$1,2,4,8,16,32,\ldots$
So,
$L_1=\{a,a^2,a^4,a^8,a^{16},\ldots\}$
This is not regular because the gap between consecutive string lengths keeps increasing.
So, $L_1$ is not regular.
For $L_2$:
$L_2=\{a^{2z}\mid z\ge 0\}$
The possible lengths are:
$0,2,4,6,8,\ldots$
So,
$L_2=\{\lambda,a^2,a^4,a^6,\ldots\}$
This language contains all strings of even length over alphabet $\{a\}$.
It can be written as:
$L_2=(aa)^*$
Since $(aa)^*$ is a regular expression, $L_2$ is regular.
For $L_3$:
$L_3=\{\omega\omega\mid \omega\in\{a,b\}^*\}$
In this language, the second half of the string must be exactly the same as the first half.
A finite automaton cannot remember the complete first half and compare it with the second half.
So, $L_3$ is not regular.
Therefore, only $L_2$ is regular.