Verifikasi Untai Dyck dengan Pushdown Automata

Abstract

Penelitian ini menerapkan pushdown automata untuk memverifikasi untai Dyck q-er, yang merupakan untai kombinatorial atas alfabet {0,1} yang diawali oleh 1, selanjutnya pada sebarang proper prefiksnya berlaku banyak 0 tidak melebihi (q − 1) kali banyaknya 1, dan pada untai utuhnya banyak 0 adalah (q − 1) kali banyaknya 1.