The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 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 O) accepted by the following automaton.

The order of $L_1$ is ____

asked in Theory of Computation by Boss (18.1k points)
edited by | 2.7k views
Is it $2$?

L= eps + 0(00)*

L2 = 0*

L3 = L2.L = 0*.(eps+0(00)*) = 0*

since, L2=L3

order = 2

Can order be zero?

See this...

4 Answers

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

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


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







Order of L is 2 such that $L^2=L^{2+1}$
answered by Veteran (55.2k points)
selected by
What does order mean ?

@Praveen Sir plz explain..
They have defined a new terminology "Order of a language" in the question itself.

Order is nothing but smallest value of k 

Which is aldready given in the question 

+9 votes
$L^3_{1} = L^2_{1}.L_{1} =  0^* \bigcup \{\epsilon, 0, 000, 00000,.....\} = 0^*$


So, $k$ = Order of $L_{1} = 2$.
answered by Veteran (55.4k points)
edited by
+1 vote
Ans: 2
answered by Active (1.2k points)
+1 vote

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



answered by (173 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,824 questions
46,798 answers
58,892 users