1. urestricted -> turing machine

  2. context-sensitive -> linear bounded automaton (LBA)

  3. context-free -> pushdown automaton (PDA)

  4. 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?)


The stack in a pushdown automaton is not bounded in general. For example, consider the machine which accepts $\{a^nb^n : n \geq 0\}$ by pushing and then popping $A$s. Indeed, if the stack is guaranteed to be bounded, then we might as well store it as part of the state, converting the PDA into an NFA.

However, by tweaking the PDA, we can ensure that the depth of the stack is linear in the number of symbols read so far, and in particular, linear in the input size. This allows us to simulate the PDA on an LBA, by using a "parallel track".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.