GATE 2018 CS – Question 62
Given a language $L$, define $L^i$ as follows: $L^0=\{\varepsilon\}$ and $L^i=L^{i-1}\cdot L$ for all $i>0$. The order of a language $L$ is defined as the smallest $k$ such that $L^k=L^{k+1}$.
Consider the language $L_1$ (over alphabet 0) accepted by the automaton in the figure.
The order of $L_1$ is ________.

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 2
Explanation
The automaton accepts the empty string and every string of an odd number of 0's, so
$$L_1=\{\varepsilon\}\cup\{0^{2k+1}\mid k\ge0\}.$$
Compute the powers:
- $L_1^0=\{\varepsilon\}$.
- $L_1^1=L_1$: the empty string and odd lengths. The string $00\notin L_1$.
- $L_1^2=L_1\cdot L_1$: odd + odd gives every even length $\ge2$, and $\varepsilon$ + odd gives every odd length. So $L_1^2$ contains $\varepsilon$ and all $0^n$: $L_1^2=0^*$.
- $L_1^3=L_1^2\cdot L_1=0^*\cdot L_1=0^*$.
$L_1^0\ne L_1^1$ and $L_1^1\ne L_1^2$, but $L_1^2=L_1^3$. The smallest $k$ with $L^k=L^{k+1}$ is $k=\mathbf{2}$.