Is it $2$?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 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 ____

+24 votes

Best answer

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

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

+7 votes

L^1 = {null, 0, 000, 00000,.....}

L^2= L.L = {null, 0, 000, 00000,.....}.{null, 0, 000, 00000,.....} = 0*

L^3 = L^2.L = 0* U {null, 0, 000, 00000,.....} = 0*

L^2=L^3

So Order would be 2.

L^2= L.L = {null, 0, 000, 00000,.....}.{null, 0, 000, 00000,.....} = 0*

L^3 = L^2.L = 0* U {null, 0, 000, 00000,.....} = 0*

L^2=L^3

So Order would be 2.

0 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**

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 435
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,161 questions

43,620 answers

124,004 comments

42,880 users