retagged by
20,502 views
78 votes
78 votes

Given a language $L$, define $L^i$ as follows:$$L^0 = \{ \varepsilon \}$$$$L^i = L^{i-1}  \bullet L \text{ 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 following automaton.

The order of $L_1$ is ________.

retagged by

4 Answers

Best answer
116 votes
116 votes
$L_1=\{\epsilon +0(00)^\ast\}$

Now that is given language $L$,  we have find order of it.

$L^0=\{\epsilon\}$

$L^1 =L^0.L=\{\epsilon \}.\{\epsilon +0(00)^\ast\}=\{\epsilon+0(00)^\ast\}$

$L^2=L^1.L=\{\epsilon+0(00)^\ast\}.\{\epsilon+0(00)^\ast\}$

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

$L^2=\{0^\ast\}$

$L^3=L^2.L=\{0^\ast\}.\{\epsilon+0(00)^\ast\}$

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

$L^3=\{0^\ast \}$

Order of $L$ is $2$ such that $L^2=L^{2+1}$
edited by
23 votes
23 votes
$L^1_{1}=\{ϵ,0,000,00000,.....\}$
$L^2_{1}=L_{1}.L_{1}=\{ϵ,0,000,00000,.....\}.\{ϵ,0,000,00000,.....\}=0^∗$
$L^3_{1} = L^2_{1}.L_{1} =  0^* \bigcup \{\epsilon, 0, 000, 00000,.....\} = 0^*$

$L^2_{1}=L^{2+1}_{1}=L^3_{1}$

So, $k$ = Order of $L_{1} = 2$.
edited by
5 votes
5 votes

L={ϵ+0(00)*} (i.e Odd Number of zero)

L^2= L*L= {ϵ+0(00)*} * {ϵ+0(00)*} = {ϵ+0(00)*+0(00)*0(00)*}

  • Here   0(00)* = odd number of zero
  • 0(00)*0(00)*= even number of zero
  • ϵ+0(00)*+0(00)*0(00)*= Even 0's+Odd 0's which is equal to 0*

so L^2=0*

L^3= L^2*L= {0*}{ϵ+0(00)*}=0*

L^2= L^(2+1)  (Given L^k=L^(k+1) i.e Order)

so the Order is 2

 

 

1 votes
1 votes

$L_{1}$ = nothing, or odd number of zeroes = $ϵ + 0(00)^{*}$

$L_{1}^{0}$ = $ϵ$    //given

$L_{1}^{1}$ = $ϵ.\{ϵ + 0(00)^{*}\}$ = $ϵ + 0(00)^{*}$

$L_{1}^{2}$ = $\{ϵ + 0(00)^{*}\}.\{ϵ + 0(00)^{*}\}$ = $0^{*}$

$L_{1}^{3}$ = $0^{*}.\{ϵ + 0(00)^{*}\}$ = $0^{*}$

 

We see that $L_{1}^{2}$ = $L_{1}^{3}$

Hence, as defined, order of the language is 2.

edited by
Answer:

Related questions