Counting Accepters

A counting accepter is a pushdown accepter M=(Q,S,{D },P,I,F) with only one-symbol stack alphabet. A configuration (q,j ,D ^k) of a counting accepter is abbreviated to (q,j ,k) and k is called the count. Instead of

write(D ,q) and read(D ,q) we write simply : up(q) and down(q)

Counting accepter for the parenthesis language:

1] scan ((, 2)(), 3) 2] up (1) 3] down (1)

Counting accepters are intermediate in power between finite-state accepters and pushdown accepters. In particular, there is a counting accepter that recognizes the parenthesis language L_p, but no counting accepter that recognizes the double parenthesis language L_dp.

Back to Table of contents of Chapter6