GATE CS 2018 Q52 — Regular and Context-free Languages

The given automaton has three states: $q_0$ (start and final state), $q_1$ (non-final state), and $q_2$ (final state), with transitions forming a cycle of length 3: $q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_0$.

Thus, the language $L_1$ consists of all strings $0^n$ where $n \not\equiv 1 \pmod 3$:

Now, let us compute the powers of $L_1$:

• $L_1^0$: $\{\varepsilon\}$
• $L_1^1$: $\{\varepsilon, 0^2, 0^3, 0^5, 0^6, 0^8, 0^9, \dots\}$
• $L_1^2 = L_1 \bullet L_1$: Since $\varepsilon \in L_1$, we have $L_1 \subseteq L_1^2$. The lengths of non-empty strings in $L_1^2$ are formed by the sum of any two lengths from $L_1$. Since $2 \in L_1$ and $3 \in L_1$, any integer $n \ge 2$ can be expressed as $2a + 3b$ for non-negative integers $a, b$. Thus, all lengths $\ge 2$ are present: $$L_1^2 = \{\varepsilon\} \cup \{0^n \mid n \ge 2\}$$
• $L_1^3 = L_1^2 \bullet L_1$: Since the minimum non-zero length in $L_1$ is 2, any non-zero string in $L_1^3$ must have length at least 2. Since $\varepsilon \in L_1$, we have $L_1^2 \subseteq L_1^3$. Thus: $$L_1^3 = \{\varepsilon\} \cup \{0^n \mid n \ge 2\}$$

Since $L_1^2 = L_1^3$, the smallest $k$ such that $L_1^k = L_1^{k+1}$ is $2$.