I need to give an example of a language $B$ is $NL-complete$ where $B^* \in L$.

I know $PATH$ is $NL-complete$ (but not limited to using other languages).

I am clueless about that. I know $L$ is not closed under $^*$ so there must a language like that.

Any help would be appreciated.


1 Answer 1


Let $\Sigma=\{0,1\}$. Take any NL-complete language $C \subset \Sigma^*$ and consider $B = C \cup \{0,1\}$. Clearly $B$ is still NL-complete (since $|B \, \Delta \, C| \le 2)$ and you have $B^* \supseteq \{0,1\}^* = \Sigma^*$, i.e., $B^* = \Sigma^* \in L$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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