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

Question

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

Answer 1

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$.