Question 62

Examine the automaton for language $L_1$ over $\{0\}$:

• State 0 is the start state and is accepting $\implies \varepsilon \in L_1$ (string of length 0).
• On '0', state 0 transitions to state 1, which is accepting $\implies 0 \in L_1$ (length 1).
• On '0', state 1 transitions to state 2, which is non-accepting $\implies 00 \notin L_1$ (length 2).
• On '0', state 2 transitions back to state 1 (accepting) $\implies 000 \in L_1$ (length 3).
  Continuing around the 2-cycle between states 1 and 2, all odd lengths $1, 3, 5, \dots$ are accepted, while even positive lengths $2, 4, 6, \dots$ are rejected.

Thus, $L_1 = \{0^n \mid n = 0 \text{ or } n \text{ is odd}\} = \{\varepsilon, 0, 0^3, 0^5, 0^7, \dots\}$.

Compute powers of $L_1$:

• $L_1^1 = L_1 = \{\varepsilon, 0, 0^3, 0^5, \dots\}$
• $L_1^2 = L_1 \cdot L_1$: Contains all lengths formed by the sum of two lengths from $\{0, 1, 3, 5, \dots\}$.
  • Even lengths: $1 + 1 = 2$, $1 + 3 = 4$, $1 + 5 = 6$, and in general $1 + (2m-1) = 2m$ for any $m \ge 1$.
  • Odd lengths: $0 + (2m+1) = 2m+1$ for any $m \ge 0$.
    Thus, $L_1^2$ contains all non-negative integer powers: $L_1^2 = \{0\}^*$.

Since $L_1^2 = \{0\}^*$, any further power is:

Because $L_1^1 \neq L_1^2$ (as $00 \notin L_1^1$ but $00 \in L_1^2$) and $L_1^2 = L_1^3$, the smallest integer $k$ satisfying $L_1^k = L_1^{k+1}$ is $k = 2$.