Which of the following are context free? , ISRO 2017 A = {anbnambm | m, n>=0}…
2017
Which of the following are context free? , ISRO 2017
A = {anbnambm | m, n>=0}
B = {ambnambn | m, n>=0}
C = {ambn | m≠2n,m, n>=0}- A.
A and B only
- B.
A and C only
- C.
B and C only
- D.
C only
Attempted by 31 students.
Show answer & explanation
Correct answer: B
Language A is formed by concatenating two context-free languages, a^n b^n and a^m b^m, which preserves context-freeness. Language B requires simultaneous matching of two independent counts (a^m with a^m and b^n with b^n), which a single stack cannot handle, making it non-context-free. Language C is the union of m > 2n and m < 2n, both context-free subsets, so C is also context-free. Therefore, A and C are the correct choices.