0
$\begingroup$

I am confused and got contradictory statements from various sources. It is mentioned in Page no 292, Chapter 11 A Hierarchy of Formal Languages & LBA, Peter Linz -An Introduction To Finite Automata, 5th Edition that "A language L is said to be CSL if there exists context-sensitive grammar G such that $L = L(G)$ or $L = L(G) \cup \{\varepsilon\}$." So the Language contains empty string & grammar as per Peter Linz.

In another version, I found that the production $S\to\varepsilon$ is also allowed in CSL, provided that 'S' does not appear on the right-hand side of any productions. However, several other sources like this youtube lecture (https://www.youtube.com/watch?v=i3c_2c2KFpY) explain that CSL does not contain a null string. Here in this given link (https://gyires.inf.unideb.hu/GyBITT/14/ch06s04.html) it is written that LBA accepts null string generated from a CSL.

In the book, "Theory of Computer Science: Automata, Languages and Computation" by Mishra K.L.P , third edition, Publisher-PhI, on page 299, subsection 9.8.1 that "The set of strings accepted by nondeterministic LBA is the set of strings generated by CSG, excluding null strings".

This is too much for making a complete confusion. Example:

L=$\{a^nb^nc^n| n\geq 0 \}$, whether this is CSL or Not? This language contains empty string too!

Please help me to get the right knowledge.

$\endgroup$

1 Answer 1

2
$\begingroup$

Welcome to CS.SE! I only know of the latter definition, i.e. the one allowing $S \to \varepsilon$ but disallowing $S$ in the right sides of productions. Ultimately this is done to have a nice definition in the sense that the class of context-sensitive languages forms a proper superset of the class of context-free languages. Definitions excluding the empty string to be in context-sensitive languages are a little bit less nice, in that sense.

As you found out, definitions may vary between sources and are often chosen in order to state some property or result in a particularly nice manner. This is common in mathematics and another example would be the question of including 0 in the natural numbers $\mathbb N$ or not. The thing is that usually these little changes do not really matter in the end; they do not fundamentally change the mathematical nature of the thing defined, and this is also the case with the small differences between the definitions for context-sensitive languages you encountered.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.