Gate2018 cs Q42

0. Given a language L, define Lⁱ as follows:

Lⁱ = 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₁ (over alphabet 0) accepted by the following automaton.

The order of is ___________.

Note – Numerical Type question

Answer
Comment
Array

Option : A
Explanation :
We need to find smallest value of k which satisfies
L₁^k = L₁^k+1

L₁ = ε + (00)
Try k = 0; L₁⁰ = L₁¹
ε = L₁ which is false.
So order is not 0.
Try k = 1: L₁¹ = L₁²
L₁² = L₁ Now, L₁² =(ε + 0(00)*)(ε + 0(00)*)
= ε + 0(00)* + 00(00)* = 0*
Clearly L₁² ≠ L₁
So order is not 1.
Try k = 2: L₁² = L₁³
Now, L₁³ = L₁².L₁
= 0*(ε + 0(00)*) = 0*
Clearly L₁³ = L₁²=0*
(so, order of L₁ is 2)

Forgot your password?

I agree with the Terms.