is there a linear bounded automaton the decides $A_{nfa}$?

first post here :)

I was wondering, since regular languages are context sensitive, and since linear bounded automatons can act as an acceptors for context sensitive language, is it possible or is there any linearly bounded automaton that decides $$A_{nfa}$$? if it exists how does it work?

$$A_{nfa} =$${< B, W > | B is an nfa that accepts input string w}

I am really curious and interested in understanding this concept and i have not found sufficient information in the textbook unfortunately

thank you very much for reading and sharing your knowledge with me

• Can you explain what $A_{nfa}$ means? Commented Mar 21, 2019 at 15:42
• edited and also posting here the definition:$A_{nfa} =${< B, W > | B is an nfa that accepts input string w} Commented Mar 21, 2019 at 18:28
• Hmm, it is a fairly elementary exercise to show directly that an NFA can be simulated in linear space. (But I don't see a slick argument that just uses abstract properties of the Chomsky hierarchy). Is this homework? Commented Mar 21, 2019 at 19:23

The technical details depend a bit on your encoding $$B$$ of the automaton. Let us suppose that the transitions are encoded like $$q_2a>q_4;q_3b>q_4;\dots$$; with four steps the LBA can identify the entire content of the transition without writing anything.

Your LBA could proceed like this:

1. Run to the comma that separates $$B$$ and $$W$$ and remember the automaton's start state (inside the LBA state).
2. Go further right to the first unmarked symbol.
3. Mark this first unmarked symbol, remember it.
4. Run back to the very beginning.
5. Search through $$B$$ for a left-hand side with the remembered state and the remembered symbol; then change the remembered NFA-state to the one on the right-hand side of this rule.
6. Advance to the comma and go to step 2.

This should work fine, if the automaton is deterministic. For a non-deterministic one we would miss some computations, because we alwasy choose the first possible transitions. For this, in step 5. we should add the option to ignore a matching transition and just keep searching.

The LBA should accept if it cannot find any more unmarked symbols and remembers an accepting NFA-state. It does not need any additional space, in fact it only writes on the space of $$W$$.

• thank you very much, studying your answer. i tried to give you an upvote, but apparently i need to have at least 15 reputations to upvote an helping post. so sorry Commented Mar 22, 2019 at 21:06