Question 7860 – Theory-of-Computation
April 16, 2024Question 7353 – NVS PGT CS 2017 Part-B
April 16, 2024Question 7881 – Theory-of-Computation
Given a language L, define Li as follows:
L0 = {ε}
Li = Li-1∙L for all i>0
The order of a language L is defined as the smallest k such that Lk = Lk+1.
Consider the language L1 (over alphabet 0) accepted by the following automaton.
The order of L1 is ______.
Correct Answer: A
Question 8 Explanation:
The regular expression for L1 : ϵ + 0 (00)*
Now L10 = ϵ
and L11 = ϵ . (ϵ+0 (00)*) = ϵ + 0 (00)* = L1
Now L12 =
L11 .
L1 = L1 .
L1 = (ϵ + 0 (00)*) (ϵ + 0 (00)*)
= (ϵ + 0 (00)* + 0(00)* + 0(00)*0(00)*)
= (ϵ + 0 (00)* + 0(00)*0(00)* ) = 0*
As it will contain epsilon + odd number of zero + even number of zero, hence it is 0*
Now L13 = L12 .
L1 = 0* (ϵ + 0 (00)*) = 0* + 0*0(00)* = 0*
Hence L12 = L13
Or L12 = L12+1 ,
hence the smallest k value is 2.
Now L10 = ϵ
and L11 = ϵ . (ϵ+0 (00)*) = ϵ + 0 (00)* = L1
Now L12 =
L11 .
L1 = L1 .
L1 = (ϵ + 0 (00)*) (ϵ + 0 (00)*)
= (ϵ + 0 (00)* + 0(00)* + 0(00)*0(00)*)
= (ϵ + 0 (00)* + 0(00)*0(00)* ) = 0*
As it will contain epsilon + odd number of zero + even number of zero, hence it is 0*
Now L13 = L12 .
L1 = 0* (ϵ + 0 (00)*) = 0* + 0*0(00)* = 0*
Hence L12 = L13
Or L12 = L12+1 ,
hence the smallest k value is 2.
2
3
4
5
Subscribe
Login
0 Comments