Discussion
Consider the following languages:
\(L_{1} = \{a^{n}b^{m}c^{n+m} : m, n \ge 1\}\)
\(L_{2} = \{a^{n}b^{n}c^{2n} : n \ge 1\}\)
Which one of the following is TRUE?
Answer: B
\(L_{1}\) is context-free while \(L_{2}\) is not context-free.
\(L_{1} = \{a^{n}b^{m}c^{n+m}\}\) is context-free: rewrite it as \(a^{n}b^{m}c^{m}c^{n}\), which nests a \(b^{m}c^{m}\) block inside an \(a^{n} \ldots c^{n}\) block. The grammar \(S \rightarrow aSc \mid aTc\), \(T \rightarrow bTc \mid bc\) generates it, and a pushdown automaton pushes for each a and b and pops for each c.
\(L_{2} = \{a^{n}b^{n}c^{2n}\}\) needs the counts of a, b and c compared together, like \(a^{n}b^{n}c^{n}\). A single stack cannot check both equalities, and the pumping lemma for context-free languages shows it is not context-free.
So the options calling \(L_{2}\) context-free, or \(L_{1}\) not context-free, are wrong.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development