OSDev.org

Hi,

I have a computational model for something I'm working on, and I can't seem to find a class of finite automaton on Wikipedia that does exactly what I'm thinking of, but I want to know what my model is equivalent to (i.e. what languages it can recognize.) The idea is pretty simple: it's a DFA that has a single optional operation which "unget"s a sequence of symbols back into the input sequence. This basically makes the input sequence into a stack. However, this does not make it the same as a pushdown automaton, because the "stack" is not separate from the input sequence. I think it could be simulated by a pushdown automaton if the entire input sequence were pushed in reverse order onto the stack, and then the rest of the automaton did not depend on the input sequence.

Any ideas?

Undoing pops essentially means that you don't look at the top item of the stack, but rather the top N items of the stack, which makes the algorithm a depth-first-search for a possible parsing.

However, the prototype context-free but not regular grammar of n a's and n b's can't be parsed by your system because it will always see a sequence of continuous b's in their original count, and therefore requires infinite states to parse a context-free grammar. It is therefore restricted to regular languages like its unmodified counterpart.

Combuster wrote:Undoing pops essentially means that you don't look at the top item of the stack, but rather the top N items of the stack, which makes the algorithm a depth-first-search for a possible parsing.

I'm not sure if you completely understood me; it doesn't only undo pops from the input stream: it can push an arbitrarily long sequence of arbitrary symbols back into the input stream.

Either way, it clearly can't recognize the a's/b's language, which seems to be sufficient to show that it's DFA-equivalent. I thought it was only capable of regular languages, but I didn't know how to be certain. Is there an official name for this sort of DFA that can do pushes into the input stream?

Also, if anyone wants to know, this is my attempt to formalize my VFS model. States are files, directories, and symlinks; directories and links contain the transitions (symlinks being the transitions that push their contents into the input stream,) and the input stream and current state are stored together in an extended path format.

If it's equivalent to a DFA (or anything complete in Regular Languages), you should be able to show a conversion scheme to make a DFA from a variant DFA.

Since the pushed-back data is a constant, you know exactly what state changes will follow for the data length provided.