Ein Kellerautomat ist ein endlicher Automat mit Stack-Speicher.
Der Stack ermöglicht geschachtelte Strukturen, z.B. Klammern oder Sprachen wie {anbn∣n≥0}\{a^n b^n\mid n\ge0\}{anbn∣n≥0}.