Discussion
The language \(L = \{a^{n}b^{n}c^{n} : n \ge 1\}\) is a content sensitive language. Give a content sensitive grammar for L :
Answer: B
The correct grammar is option (B).
Start with \(S \to abc\) for \(n = 1\). For larger \(n\), \(S \to aAbc\) begins a derivation, and the rules \(Ab \to bA\) and \(Ac \to Bbcc\) move \(A\) to the right past the b and turn it into one more b and c. Then \(bB \to Bb\) carries \(B\) back left to the a's, and \(aB \to aa\) ends with one more a. For \(n = 2\):
\[ \begin{aligned} S &\Rightarrow aAbc \Rightarrow abAc \\ &\Rightarrow abBbcc \Rightarrow aBbbcc \Rightarrow aabbcc \end{aligned} \]
The rule \(aB \to aaA\) restarts the cycle for larger \(n\). Option A has no rule giving \(abc\), and its \(S \to aSbc\) puts the b and c in the wrong places (it derives \(aaabbccbc\)). Option C has \(Ab \to Ab\), which changes nothing, so \(A\) never reaches the c. Option D drops the contexts: \(S \Rightarrow aAbc \Rightarrow aBbccbc \Rightarrow aabccbc\), which is not of the form \(a^{n}b^{n}c^{n}\).
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