Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Which of the following are context free language ?
(A) ${w^i x^j y^k z^l \mid i + k = j + l,; i,j,k,l \ge 0}$
(B) ${w^i x^j y^k z^l \mid i = j \text{ and } k = l,; i,j,k,l \ge 0}$
(C) ${w^i x^j y^k z^l \mid i = j = k \text{ and } k \ne l,; i,j,k,l \ge 0}$
(D) ${w^i x^j y^k z^l \mid i = j = k + l,; i,j,k,l \ge 0}$
(E) ${w^i x^j y^k z^l \mid i = j \text{ and } k \ne l,; i,j,k,l \ge 0}$
Choose the correct answer from the options given below :
Solution
(A) Condition $ i + k = j + l $ This type of dependency is not context free (requires two independent balances). So not CFL. (B) Conditions $ i = j $ and $ k = l $ Language form $ w^i x^i y^k z^k $ This is context free. (C) Condition $ i = j = k $ This is similar to $ a^n b^n c^n $ which is not context free. (D) Condition $ i = j = k + l $ Single dependency handled by PDA → Context Free. (E) Condition $ i = j $ and $ k \ne l $ Still context free (difference condition allowed). Correct CFL: (D) and (E)Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
