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 ________. Theory of Computation gatecse-2018 theory-of-computation numerical-answers regular-language 2-marks + – gatecse asked Feb 14, 2018 • retagged Dec 1, 2022 by Lakshman Bhaiya gatecse 20.7k views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply Show 15 previous comments `JEET commented Dec 12, 2019 reply Follow Share Thanks. 0 votes 0 votes swami_9 commented Jul 29, 2021 1 flag: ✌ Low quality (PreyumKr) reply Follow Share why epsilon is included in language. 0 votes 0 votes Pranavpurkar commented Jan 13, 2022 i edited by Pranavpurkar Nov 15, 2022 reply Follow Share @Sambhrant MauryaCan L1 be written as (0.(00)*)* ?No. 0 votes 0 votes Please log in or register to add a comment.
Best answer 117 votes 117 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}$ Praveen Saini answered Feb 14, 2018 • edited Jun 22, 2021 by Lakshman Bhaiya Praveen Saini comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Ravi8770071203 commented Sep 9, 2021 reply Follow Share Sir @praveen_sir how L2 = {0*} ? 0 votes 0 votes himanshud2611 commented Sep 23, 2023 reply Follow Share Given, L2 = L1.L L2 = {e + 0(00)*}.{e + 0(00)*} L2 = e + 0(00)* + 0(00)* + 0(00)*0(00)* L2 = e + 0(00)* + 0(00)*0(00)* Here, L2 covers all the cases. Number of zeroes can be: 0(as e is there), 1(as 0(00)* is there). So, all such possibilities of # of zeroes are present in it. 0 votes 0 votes Akash 15 commented Jan 20 reply Follow Share At the end the thing is that $L_1^{2}=\{0^*\}$ , $L_1^{3}=\{0^*\}$ So, $L_1^{2} = L_1^{3}=L_1^{2}.L_1=L_1^{2+1}$ So, according to given definition, $L_1^{2}=L_1^{2+1}$. Hence order of $L_1$ is $2$. 0 votes 0 votes Please log in or register to add a comment.
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$. Digvijay Pandey answered Feb 14, 2018 • edited Jul 17, 2018 by Digvijay Pandey Digvijay Pandey comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Sushant kaushal answered Jun 22, 2018 Sushant kaushal comment Share Follow See all 0 reply Please log in or register to add a comment.
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. JashanArora answered Oct 19, 2019 • edited Feb 5, 2020 by JashanArora JashanArora comment Share Follow See all 0 reply Please log in or register to add a comment.