后进先出自动机

后进先出自动机（last-in-first-out automaton），文学-语言文字-计算语言学及语料库语言学-计算语言学-形式语言-自动机等价关系，具有后进先出栈的自动机。后进先出栈实际上是一个符号暂存器，在栈中只有在栈顶才能把符号加进或抹去。当把一个符号加到栈顶时，原先处于栈最顶端的符号变成了从栈顶算起的第二个符号，而原先从栈顶算起的第二个符号变成了第三个符号，等等；当一个符号从栈顶抹去时，原先从栈顶算起的第二个符号变成了最顶端的符号，而原先从栈顶算起的第三个符号变成了第二个符号等。总之，最后加入栈顶的符号，也就是要最先抹去的符号，符号的加进或抹去，遵守着“后进先出”的原则。这种后进先出栈可以同步枪上的子弹盒相类比。子弹盒的底部有弹簧支持，弹簧的力量仅能使一颗子弹出现在子弹盒的顶端。当子弹盒顶端的子弹打出后，弹簧负荷减小，下面一颗子弹在弹簧的推动下会出现在子弹盒的顶端。如果把一颗子弹装在子弹盒的顶端，那么，子弹盒中的其他子弹就被往下推，弹簧受到压缩，因而这颗子弹就刚好与子弹盒的顶端相平。这里假定子弹盒中的弹簧是任意长的，则想加多少颗子弹都是可以的。