computation-theory - 一堆下推自动机怎么能接受一个无限大的字符串？

Question

考虑给定的语言 L={a^nb^n (a power n and b power n) |n>=1}，因此根据语言它必须包含字符串，使得 a's 和 b's 必须在连续中具有相同的频率时尚，现在假设一个字符串来了，最初 a 的数量非常大，那么我如何将如此大量的 a 存储到堆栈中，因为我们的内存量是有限的，然后当 b 出现时，我一个接一个地弹出 a .

标签： computation-theorypushdown-automatonautomaton

Answer 1

下推自动机具有无限的记忆。可以在有限数量的状态之间转换，但堆栈大小是无限的。