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.5k 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 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}$ 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 Raju Kalagoni commented Apr 3, 2018 reply Follow Share What does order mean ? @Praveen Sir plz explain.. 0 votes 0 votes Deepak Poonia commented Apr 10, 2018 reply Follow Share They have defined a new terminology "Order of a language" in the question itself. 11 votes 11 votes Kandula Tarun Reddy commented May 22, 2018 reply Follow Share Order is nothing but smallest value of k Which is aldready given in the question 0 votes 0 votes swami_9 commented Jul 29, 2021 reply Follow Share why epsilon is included in first line. 0 votes 0 votes ManInTheSuit commented Aug 31, 2021 reply Follow Share @swami_9 The Start state is also a final state in the DFA. Thus it also accepts empty string or ϵ. 0 votes 0 votes 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.