computation-theorypushdown-automatonautomaton

How can a Stack of Push Down Automata accept a string of Indefinitely Large?


Consider for the given Language L={a^n b^n (a power n and b power n) |n>=1},so according to the language it must contain strings such that a's and b's must be of equal frequencies in continuous fashion,Now suppose a string comes such that initially the number of a's are very large then how do i store such huge number of a's onto the stack,since we have finite amount of memory ,and later when b comes i pop a's one by one.


Solution

  • A pushdown automaton has infinite memory. There are a finite number of states to transition between but the stack size is unlimited.