urestricted -> turing machine
context-sensitive -> linear bounded automaton (LBA)
context-free -> pushdown automaton (PDA)
regular -> finite state machine
Hi, I am kind of confused about relation between LBA and PDA.
Is the stack in pushdown automaton bounded (not using infinite space)?
If not, how can a LBA accept a language that PDA accepts? (How can one simulate a PDA with unbounded stack using a linear bounded automaton?)