Back to the 2025 paper

Module 3: Context-Sensitive Languages

20252m

Which production is not allowed in a CSG?

(i) AB→BAAB \rightarrow BA
(ii) A→ϵA \rightarrow \epsilon
(iii) A→aA \rightarrow a
(iv) aB→aba B \rightarrow a b

Worked SolutionAI Assisted

Answer

Correct Option: (ii) A→ϵA \rightarrow \epsilon

Explanation

Context-Sensitive Grammar (CSG, Type-1): Production α→β\alpha \rightarrow \beta where α,β∈(V∪T)∗\alpha,\beta \in (V\cup T)^* and ∣α∣≤∣β∣|\alpha| \le |\beta| (non-contracting), except possibly S→ϵS \rightarrow \epsilon with SS not appearing on RHS.

Check each:

  • (i) AB→BAAB \rightarrow BA : ∣α∣=2|\alpha|=2, ∣β∣=2|\beta|=2 → 2≤22 \le 2 allowed (context-sensitive, length-preserving).
  • (ii) A→ϵA \rightarrow \epsilon : ∣α∣=1|\alpha|=1, ∣β∣=0|\beta|=0 → 1≤01 \le 0 false, contracting, not allowed in CSG (unless A=SA=S and SS is start with special ϵ\epsilon rule).
  • (iii) A→aA \rightarrow a : 1≤11 \le 1 allowed.
  • (iv) aB→abaB \rightarrow ab : 2≤22 \le 2 allowed (context aa).

Hence only A→ϵA \rightarrow \epsilon violates the monotonicity condition.

Final Answer

Not allowed: A→ϵA \rightarrow \epsilon → Option (ii).

Similar questions

AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.