Discussion
Consider the following two languages over the alphabet \(\{a, b, c\}\), where \(m\) and \(n\) are natural numbers.
\(L_{1} = \{a^{m}b^{m}c^{m+n} \mid m, n \ge 1\}\)
\(L_{2} = \{a^{m}b^{n}c^{m+n} \mid m, n \ge 1\}\)
Which ONE of the following statements is CORRECT?
Answer: C
The correct statement is \(L_{1}\) is not a context-free language but \(L_{2}\) is a context-free language.
\(L_{2} = \{a^{m}b^{n}c^{m+n}\}\) is context-free: a pushdown automaton pushes a symbol for each a and each b and pops one for each c. A grammar is \(S \rightarrow aSc \mid aBc\), \(B \rightarrow bBc \mid bc\), which wraps each a and each b with its own c.
\(L_{1} = \{a^{m}b^{m}c^{m+n}\}\) needs the a's and b's to be equal and the c's to exceed them. A single stack cannot do both: matching a's against b's uses up the count before the c's arrive. The pumping lemma confirms it with \(a^{p}b^{p}c^{p+1}\): any pumped segment of length at most p either upsets the a = b balance or, by pumping, makes the a's and b's reach or pass the number of c's, or the c's fall to the number of a's.
So only option C is right; options A and B wrongly call \(L_{1}\) context-free, and D wrongly excludes \(L_{2}\).
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