GATE 2022: Theory Of Computation Quiz-5

Consider the regular expression , what is the total number of strings generated by the language with length less than 3 ?

Let L1 and L2 be two languages. L2 is CFL. It is known that L1 is regular. Now consider four new languages A,B,C,D which are obtained by performing different operations between L1 and L2. The language A is obtained by performing Union operation between L1 and L2. The language B is obtained by performing intersection operation between L1 and L2. The language C is obtained by performing intersection operation between L2 and complement of L2. The language D is L1-L2. Among A,B,C and D , how many languages are CSL : _________.

How many of the following languages are CFL?

I. ww^R where w^R represents reverse of w

II. aⁿ where n is prime

III. a^2n-1b²ⁿ⁺¹ c^k where n,k ∈ N

IV. a^n! where n ∈ N