Given a language 𝐿, define 𝐿𝑖 as follows

Q. Given a language 𝐿, define 𝐿^𝑖 as follows:

𝐿⁰ = {𝜀}

𝐿^𝑖 = 𝐿^𝑖−1 ⋅ 𝐿 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑖 > 0

The order of a language L is defined as the smallest k such that 𝐿^𝑘 =    𝐿^𝑘+1. Consider the language L₁ (over alphabet 0) accepted by the following automaton.

The order of L₁ is

Ans: 2

Sol:

L1 = ε + 0(00)*
L⁰ = ε
L¹ = ε . (ε + 0(00)*)
    = ε + 0(00)* = L1

L² = L¹ . L1 = L1 . L1
    = (ε + 0(00)*) (ε + 0(00)*)
    = ε + 0(00)* + 0(00)* + 0(00)* . 0(00)*
    = ε + 0(00)* + 0(00)* 0(00)* = 0*

Given automaton contains epsilon and even number of 0’s and odd numbers of 0’s.

L³ = L² . L1
    = {0*} . {ε + 0(00)*} = 0* 0(00)* = 0*
So, L² = L³ = L²⁺¹
So, smallest value of k = 2