MadeEasy Test Series 2018: Theory of Computation - Identify Class Language

Question

a) Only L1 is correct

b)Only L2 is correct

c)Both L1 and L2 are correct

d)None of L1 and L2 is correct

My question is: What is meant by prefix of string? And how is L1 regular?

Comments

if you observe the string generated by L1 you will find that it is a set of string which can contain only 1 time 2 consecutive a’s or b’s and DFA can be formed for this language. easily so this is a regular language

Answer 1

DFA can be drawn for the first  Language L1 and so the language is regular.

L1 will have finite no. of strings in the language .

L1= { € ,a ,aa, b, bb , ab , aab , aabb , aabbb,  aabbbb }

Language second is clearly a cfl language .

L2 can be written as -

L2= (€ + a + aa)(a^n b^n)  

(Second part is the standard example of cfl language)

[   ' € '   represents null string   ]