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 $ arepsilon$ and all odd powers: $L_1={ arepsilon}cup{0^{2k+1}}$. Then $L_1^2$ contains every $0^n$ (for example $00=0cdot0$), and so does $L_1^3$, but $L_1
e L_1^2$ because $00
otin L_1$. So the order is 2.