Question

Given a language L, define $L^i$ as follows:

$L^0=\left\{ϵ\right\}$

$L^i=L^{i-1}\cdot Lforalli>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 following automaton.

The order of $L_1$ is

Answer 1

We need to find smallest value of k which satisfies

$L_1^k=L_1^{k+1}$

$L_1=ϵ+0(00{)}^{\ast }$

Try $k=0:L_1^0=L_1^1$

$\Rightarrow ϵ=L_1$ which is false.

So order is not 0.

Try k = 1; $L_1^1=L_1^2$

$\Rightarrow L_1^2=L_1$

Now, $L_1^2=(ϵ+0(00{)}^{\ast }\left)\right(ϵ+0\left(00{)}^{\ast }\right)$

= $ϵ+0(00{)}^{\ast }+00(00{)}^{\ast }=0^{\ast }$

Clearly $L_1^2\ne L_1$

So order is not 1.

Try k = 2: $L_1^2=L_1^3$

Now, $L_1^3=L_1^2.L_1$

= $0^{\ast }(ϵ+0(00{)}^{\ast })=0^{\ast }$

Clearly $L_1^3=L_1^2=0^{\ast }$

(So order of $L_1$ is 2)