Consider the following languages :

L_{1} = {a^{m} b^{n} | m ≠ n}

L_{2} = {am bn | m = 2n + 1}

L_{3} = {am bn | m ≠ 2n}

Which one of the following statement is correct ?

This question was previously asked in

UGC NET Paper 3: Computer Science Nov 2017 Official Paper

Option 4 : L_{1}, L2 and L3 are context free languages

The correct answer is **option 4.**

__Key Points__

**L1 = {am bn | m ≠ n}**

- It means m could be greater than (m>n) or less than 'n' (m<n)but m will not be equal to 'n'(m=n).
- Since for accepting L1, we need storage so then a number of 'a' can be stored in it and when b's come as input a's and b's can be compared.
- Since
**finite automata**do**not**have a**storage**element hence language is**not regular.**

**L2 = {am bn | m = 2n + 1}**

L2 rewrite as** {a2n+1bn }.**

Here skip the first **'a'. **If the input string reaches an empty symbol then it accepts the language(**string: a**) or if the input symbol is 'a' stores all a's in the stack. After every 'b' pop the two a's until it reaches the empty symbol then it accepts the language.

Hence the language L_{2 } is CFL.

**L3 = {am bn | m ≠ 2n}**

It means m could be greater than **(m>2n)** or less than 'n' **(m<2n)** but m will not be equal to 'n'(m=n). Store all a's in the stack and for two b's pop one 'a'. If if there any a's in the stack **(m>2n)** or the top of the stack is Z_{0} and the input symbol is not reached to the empty symbol **(m<2n)** then it is accepting the language.

Hence the language L3 is CFL.

**Hence the correct answer is*** L1, L2 and L3 are context-free languages.*

Official Paper 1: Held on 24 Sep 2020 Shift 1

17128

50 Questions
100 Marks
60 Mins