New answers tagged


You got the definition of $L^+$ wrong. It is not $L^* \setminus \{\epsilon\}$. Rather, it is $$ L^+ = \bigcup_{n=1}^* L^n. $$ You can check that $\epsilon \in L^+$ iff $\epsilon \in L$. Therefore: If $\epsilon \notin L$ then $L^+ = L^*\setminus\{\epsilon\}$. If $\epsilon \in L$ then $L^+ = L^*$.


Linear-bounded automata accept the class of context-sensitive languages. In contrast, Turing machine (deterministic as well as nondeterministic) accept the class of recursive languages. Every context-sensitive language is recursive, but the converse doesn't hold. For example, the halting problem for nondeterministic Turing machines running in space $n^2$ is ...

Top 50 recent answers are included