3.3k views

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 ____

edited | 3.3k views
0
Is it $2$?
+7

L= eps + 0(00)*

L2 = 0*

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

since, L2=L3

order = 2

+1
Can order be zero?
+11

See this...

0

Can L1 be written as (0.(00)*)* ?

0
No,  because (0.(00)*)* is simply 0* which is not actually L1
0
I've a small doubt
how did ϵ+0(00)*+0(00)*0(00)* become 0*?
0
ϵ+0(00)*+0(00)*0(00)*  ⇒ ε + all odd number of zeros and all even number of zeros.

∴ it is 0*   .☺
0
then shouldn't it be 0+ ?
+1
$\epsilon$ is there.

So it will be $\varepsilon +0^+$.

So it will be 0*.
0

0
oh got it now thanks :)

$L_1=\{\epsilon +0(00)^*\}$

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

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

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

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

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

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

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

$=\{0^*+0^*0(00)^*\}$

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

Order of L is 2 such that $L^2=L^{2+1}$
selected
0
What does order mean ?

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

Order is nothing but smallest value of k

Which is aldready given in the question

$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
Ans: 2

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