GATE CSE 2018 | Question: 52

Question

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 ________.

Comments

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...

---

Can L₁ be written as (0.(00)*)* ?

---

No,  because (0.(00)*)* is simply 0* which is not actually L1

---

I've a small doubt
how did ϵ+0(00)*+0(00)*0(00)* become 0*?

---

ϵ+0(00)*+0(00)*0(00)*  ⇒ ε + all odd number of zeros and all even number of zeros.

∴ it is 0*   .☺

---

then shouldn't it be 0+ ?

---

$\epsilon$ is there.

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

So it will be 0*.

---

@aditi19 u r getting right??

---

oh got it now thanks :)

---

2...

---

I think it can also be written as: $\mathbf{\epsilon+0+0(00)^*}$

Even though it is equivalent to $\mathbf{\epsilon + 0(00)^*}$

Check once @Verma Ashish

 

---

@`JEET  If you are talking about L1, then you are right.. 

---

Thanks.

---

why epsilon is included in language.

---

@Sambhrant Maurya

Can L₁ be written as (0.(00)*)* ?

No. 

---

Answer 1

$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}$

Comments

Sir @praveen_sir how L2 = {0*} ?

---

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.

---

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$.

Answer 2

$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$.

Answer 3

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^²= L^⁽²⁺¹⁾  (Given L^^k=L^^(k+1) i.e Order)

so the Order is 2

 

 

Answer 4

$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.