Question

Does CSL contains empty string ? I've got contradictory statements from various sources.
Can someone for sure say whether empty string is CSL or not ! Please give the reference.

My source -> Page no 292, Chapter 11 A Hierarchy of Formal Languages & LBA, Peter linz -An Introduction To Finite Automata, 5th Edition

"A language L is said to be CSL if there exists context sensite grammar G such that L = L(G) or L = L(G) U { }" So Language contains empty string & Grammar does not ! as per Peter Linz "

Here

means empty string.

Example ->

a^nb^nc^n , n >=0, where this is CSL or Not ? This language contains empty string too !

Comments

Clearly CSL contains empty string. Now, does CSG contain empty string? As per normal definition of CSG it does not - but many places include it as an extra condition. Anyway GATE does not ask for definition - so CSL contains empty string is all that matters.

---

@Bishnu

---

null productions are not allowed in type 1 grammer by definition,but - 

to allow "NULL PRODUCTIONS" , NT --> ε is allowed only if that NT does not appear in RHS of any production to satisfy | LHS | <= | RHS |  

another formal definition 

αAβ ---> αγβ such that 

alpha is (T, NT)* , A is (T,NT), beta is (T,NT)*  

we can say that , "A IS CHANGED TO GAMMA IN PRESENCE OF ALPHA AND BETA where alpha and beta are left and right context resp"

Answer 1

Yes, it is CSL. Because empty string must be a regular language. When a string is regular and also finite, it also satisfies higher properties like CFL, CSL and also recursive

∊⊂ finite ⊂ regular ⊂ CFL ⊂ CSL.

Comments

I think it is not. please refer this https://en.wikipedia.org/wiki/Context-sensitive_grammar, in formal defination section

---

It's CSL but not CSG. A stated in Linz,

Answer 2

Yes, CSL do contain empty string.
But with restriction that only the production of the form S->e are valid and S should not occur on the right hand side of any production (in this case). Just to include, empty string in the grammar, this production is used.

Answer 3

i guess yes it does. even it accepts production like S->epsilon but S should not appear right side of any production.