Discussion
Consider the following languages:
\[ \begin{aligned} \text{I. } & \{a^{m}b^{n}c^{p}d^{q} \mid m + p = n + q, \\ & \text{where } m, n, p, q \ge 0\} \end{aligned} \]
\[ \begin{aligned} \text{II. } & \{a^{m}b^{n}c^{p}d^{q} \mid m = n \text{ and } p = q, \\ & \text{where } m, n, p, q \ge 0\} \end{aligned} \]
\[ \begin{aligned} \text{III. } & \{a^{m}b^{n}c^{p}d^{q} \mid m = n = p \text{ and } p \neq q, \\ & \text{where } m, n, p, q \ge 0\} \end{aligned} \]
\[ \begin{aligned} \text{IV. } & \{a^{m}b^{n}c^{p}d^{q} \mid mn = p + q, \\ & \text{where } m, n, p, q \ge 0\} \end{aligned} \]
Which of the languages above are context-free?
Answer: B
The context-free languages are I and II only.
I: \(m + p = n + q\) says the a's and c's together balance the b's and d's. A pushdown automaton can push a symbol for each a, cancel against each b (pushing a different marker once the a's run out), and do the same for the c's and d's, accepting when the stack is empty, so I is context-free.
II is the concatenation of \(\{a^{m}b^{m}\}\) and \(\{c^{p}d^{p}\}\), both context-free, so it is context-free.
III is not: intersecting it with the regular language \(a^{*}b^{*}c^{*}\) (forcing \(q = 0\)) leaves \(\{a^{n}b^{n}c^{n} : n \ge 1\}\), which is not context-free, and context-free languages are closed under intersection with regular languages. IV is not either: with \(q = 0\) it becomes \(\{a^{m}b^{n}c^{mn}\}\), which needs a product of two counts. So the options containing III or IV 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