A Context-Sensitive Grammar (Type-1) contains production rules of the form $\alpha → \beta$. What restriction is placed on string lengths |$\alpha |$ and |$\beta |$?
Type-1 grammars are non-contracting: length of RHS |$\beta | must be$ at least length of LHS |$\alpha | (|\alpha | \le |\beta |)$.
What formal machine model recognizes Context-Sensitive Languages (CSLs)?
Linear Bounded Automata (nondeterministic TMs with tape bounded to k $\times |w|) recognize Context-Sensitive Languages$.
Is the Membership Problem ('Is w ∈ L?') DECIDABLE for Context-Sensitive Languages?
Because tape length is bounded to k $\times |w|$, the total number of distinct LBA configurations is finite, permitting decidable loop/halt detection.
Is the Emptiness Problem ('Is L = ∅?') Decidable for Context-Sensitive Languages?
Testing whether an LBA accepts zero strings is an undecidable problem.
In Kuroda Normal Form, every Context-Sensitive Grammar production is restricted to which four production shapes?
Kuroda normal form restricts CSL rules to length-2 non-terminal swaps AB → CD, CNF-like non-terminal splits A → BC, single terminals A → a, and start null S → $\epsilon$.