Every context-sensitive language $\subseteq \Sigma^* = \{a,b\}^*$ can be expressed using an essentially non-contracting grammar. With just one non-terminal symbol, we can't express all context-sensitive languages.

Does there exist a minimum $k$, such that all context-sensitive languages can be expressed as a non-contracting grammar with $k$ non-terminal symbols?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.