Steve Find said on August 09, 2002 6:24 PM: >Anyone happen to know where pushdown automata fit in this list? Can >they handle context-sensitive, just context-free, or some other >subset?
Mark Reed said on August 09, 2002 7:60 PM: >To recognize a context-sensitive language I think you need a Turing >machine. I'm not aware of anything intermediate in power between >a PDA and a TM. A regular expression is equivalent to an FSM (Finite State Machine). A context-free grammar is equivalent to a PDA (Push-down Automata -- i.e., an FSM with a stack) A context-sensitive grammars is equivalent to an LBA (Linear Bounded Automata -- i.e., a Turing machine restricted to a given finite length of tape) An unrestricted grammar is equivalent to a TM (Turing Machine). [info from _Introduction_to_Automata_Theory,_Languages,_and_Computation_, John E. Hopcroft and Jeffrey D. Ullman]
