Tài liệu Ôtômát đẩy xuống

Có hay không lớp ôtômát tương ứng với lớp NNPNC?
Như đã biết, ôtômát hữu hạn không thể nhận biết tất cả
NNPNC, chẳng hạn L = {anbn : n ≥ 0}, vì nó có một bộ
nhớ hữu hạn. Vì vậy chúng ta muốn có một máy mà đếm
không giới hạn.
Từ ví dụ ngôn ngữ {wwR}, chúng ta cần thêm khả năng
lưu và so trùng một dãy kí hiệu trong thứ tự ngược lại.
Điều này đề nghị chúng ta thử một stack như một cơ chế
lưu trữ. Đó chính là lớp ôtômát đẩy xuống (PushDown
Automata - PDA)