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 ________.
@Sambhrant Maurya
Can L1 be written as (0.(00)*)* ?
No.
L={ϵ+0(00)*} (i.e Odd Number of zero)
L^2= L*L= {ϵ+0(00)*} * {ϵ+0(00)*} = {ϵ+0(00)*+0(00)*0(00)*}
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
$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.
64.3k questions
77.9k answers
244k comments
80.0k users