Teoretycznie, czytając wystarczająco długi ciąg liter, komputer w końcu przepełni całą swoją pamięć licznikiem ile liter do tej pory przeczytał. W tym momencie będzie musiał znaleźć się ponownie w już raz odwiedzonym stanie. Ten przykład pokazuje jak wyniki dotyczące języków regularnych odnoszą się do klasycznych komputerów.
Siła automatów ze stosem Języki rozpoznawane przez automaty ze stosem nazywane są językami bezkontekstowymi. Równoważną definicją tej klasy jest określenie jej jako języków definiowanych przez gramatyki bezkontekstowe. Języki te obejmują wszystkie języki regularne i część języków nieregularnych (jak np. podany wyżej język zawierający równą liczbę liter ‘a’ i ‘b’). Istnieją jednak języki, których automaty ze stosem nie potrafią rozpoznawać – przykładem jest np. język liczb pierwszych. Ogólnie do pokazywania, że jakiś język nie jest bezkontekstowy można wykorzystać lemat o pompowaniu dla języków bezkontekstowych.