Ace Test Series: Theory Of Computation - Identify Class Language

Question

The answer is given as B.. I understand that CSL is linear bounded automata. But can you explain why it cannot accept null string?.Is it because LBA or turing machine do not recognize epsilon moves?

Comments

According to Chomsky hierarchy $\epsilon$ productions are not CSL.

because production like A->$\epsilon$

length of left side is <=length of right side for CSL,but here |A|=1 and |$\epsilon$|=0.

it violates CSL so it is removed .

---

Just wanted to reverify this. Are you sure there is no A->ϵ production in CSL? I think it is allowed if A is not on right side of any production.

---

In addition, a rule of the form

S → λ

where λ represents the empty string and S does not appear on the right-hand side of any rule is permitted. The addition of the empty string allows the statement that the context sensitive languages are a proper superset of the context free languages, rather than having to make the weaker statement that all context free grammars with no →λ productions are also context sensitive grammars.
     https://en.wikipedia.org/wiki/Context-sensitive_grammar

Answer 1

ohk now first thing is stop  solving TOC and CO questions from any test series else u'll mess up ur concepts..
now lets see...CSL and CSG...
according to conventions ,CSG doesnt contain any epsilon productions..but does it mean CSL also dont have epsilon?
certainly nt...isnt epsilon regular?
isnt every regular CSL also?

conclusion:epsilon is very much CSL but CSG doesnt have any epsilon production!!!
 

Comments

thanks for clarification!

---

that is what i thought. so tired of these test series questions!!..they seriously mess up your understanding.Thanks so much for the clarification!!