Back to the 2023 paper

Module 3: Context-Sensitive Languages

20232m

The language {anbncn+m∣m,n≥1}\{ a^n b^n c^{n+m} \mid m, n \ge 1 \} is:

(i) regular
(ii) context-free but not regular
(iii) context-sensitive but not context-free
(iv) type 0 but not context-sensitive

Worked SolutionAI Assisted

Answer

Correct Option: (iii) Context-sensitive but not context-free (and hence not regular)

Explanation

L={anbncn+m∣m,n≥1}={anbnck∣k=n+m>n}L = \{ a^n b^n c^{n+m} \mid m,n \ge 1 \} = \{ a^n b^n c^{k} \mid k = n+m > n \}.

Not Context-Free

Assume LL is CFL, let pp be pumping length. Take w=apbpcp+1∈Lw = a^p b^p c^{p+1} \in L (n=p,m=1n=p, m=1). By pumping lemma for CFL, w=uvxyzw = uvxyz with ∣vxy∣≤p|vxy|\le p, ∣vy∣>0|vy|>0. Pumping must stay within first pp aa's or bb's or cc's. Any pumping changes counts and breaks condition #c>#a=#b \#_c > \#_a = \#_b (or breaks anbna^n b^n). Formal proof shows LL not CFL. Equivalent to anbncna^n b^n c^n (which is not CFL) with extra cmc^m tail; intersection with regular a∗b∗c∗a^*b^*c^* does not help but L∩a∗b∗cpL \cap a^*b^*c^p style shows non-CFL.

Context-Sensitive

It is accepted by Linear Bounded Automaton. Grammar is context-sensitive:

S→aSBC∣aBCS \rightarrow a S B C \mid a B C
CB→BCCB \rightarrow BC
aB→aba B \rightarrow a b
bB→bbb B \rightarrow b b
bC→bcb C \rightarrow b c
cC→ccc C \rightarrow c c

This is Type-1 (CSG) but not Type-2. It is decidable but not CFL.

Final Answer

CSL but not CFL → Option (iii). Also not regular; ultimately Type-1 in Chomsky hierarchy.

Similar questions

Student FinanceWeb Platform

Pocketly — Personal Finance for Students

Keep your hostel and college expenses under control. Track accounts, log spending in seconds, and stay within your monthly budget.