GATE Computer Science (CS) 2018 Shift 1 Solved Paper

Question : 50 of 65

Marks: +1, -0

Given a language

{L}

, define

L^{i}

as follows:

L^{0}=\{∈\}

L^{i}=L^{i-1} . L

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

Solution:

We need to find smallest value of

{k}

which satisfies

L_{1}^{k}=L_{1}^{k+1}

L_{1}=E+(00)^{*}

Try

k=0 ; \;\; L_{1}^{0}=L_{1}^{1}

⇒ \;\; ∈=L_{1}

Which is false.
So order is not 0 .
Try

k=1: \;\; L_{1}^{1}=L_{1}^{2}

⇒ \;\; L_{1}^{2}=L_{1}

Now,

\;\; L_{1}^{2}=(E+0(00)^{*})(E+0(00)^{*})

=E+0(00)^{*}+00(00)^{*}=0^{*}

Clearly

\;\; L_{1}^{2} ≠ L_{1}

So order is not 1 .
Try

k=2: \;\; L_{1}^{2}=L_{1}^{3}

Now,

L_{1}^{3}=L_{1}^{2} ⋅ L_{1}

=0 *(E+0(00)^{*})=0^{*}

Clearly

L_{1}^{3}=L_{1}^{2}=0^{*}

(So, order of

L_{1}

is 2)

Go to Question:

Prev Question

Next Question