# Is every linear language in NL?

I wonder if all the linear languages are in NL?

I was thinking that we can take an input-language $$L$$ and convert it to linear normal form. If this is not possible, the machine rejects. If the language can be written in linear normal form, the machine accepts. The work tape only needs to store the current production, so that it works in logarithmic time.

Am I completely lost or is this a good start?

• What is a linear language? Is it a language that can be decided in O(n) time? Jun 5, 2020 at 16:25
• No, it is a language that can be produced by a linear grammar $G=(V,\Sigma,R,S)$, with rules that are only on the forms $A\to uBv$ and $A\to u$ where $A,B\in V$ and $u,v\in\Sigma^*$. Jun 5, 2020 at 17:00
• Can you edit your post to elaborate on how you would construct the Turing machine and how you know it uses logarithmic space?
– D.W.
Jun 5, 2020 at 18:36