[FOM] finite automata equipped with bags:

Kreinovich, Vladik vladik at utep.edu
Sat Aug 23 20:24:18 EDT 2008

Dear Friends,

Undergraduate theory of computation courses usually starts with finite
(FA), pushdown automata (FA equipped with a stack into which he can push
symbols and from which we can pop symbols), and Turing machines (FA with
a tape
or, equivalently, with two stacks). It is well understood what languages
recognized by such devices.

A natural question is: what happens if, instead of a stack, we equip a
automaton with a bag (= multi-set = a generalization of a set in which
we can
have multiple copies of each element). The resulting non-deterministic
can push a symbol into a bag, pop (non-deterministically) a symbol from
a bag,
and check whether a bag is empty. What languages can be recognized by
such a

This idea was proposed by my colleague Amitawa Biswas in 2005; he is
analyzing this new device and working on a related paper.

At least some languages not recognizable by a pushdown automata (PDA)
can be
recognized by such a device. For example, a textbook example a language
cannot be recognized by a PDA is L = {a^n b^n c^n}. To recognize this
in a new device, we first get into an "a" state in which, upon seeing an
symbol, we push this symbol into the bag; upon seeing "b", we get into a
state in which, upon seeing every "b" symbol, we pop an "a" and push a
upon seeing a symbol "c", we get into a "c" state in which, upon seeing
symbol "c", we pop a symbol from a bag and, if the popped symbol is "b",
continue. We accept the word if we are in the final state "c" and the
bag is

Amitawa thinks that probably all context-free languages can be
recognized by
this new device; maybe it is equivalent to a Turing machine, but he has
not yet
been able to prove that.

Since the idea seems natural, he tried to google similar papers but has
found anything relevant yet.

Any references and/or comments will be greatly appreciated.

Please send your replies to me at vladik at utep.edu and to Amitawa at
abiswas at utep.edu

Many thanks


More information about the FOM mailing list