[FOM] finite automata equipped with bags:

[Kreinovich, Vladik]

Dear Friends,

Undergraduate theory of computation courses usually starts with finite
automata
(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
can
recognized by such devices.

A natural question is: what happens if, instead of a stack, we equip a
finite
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
machine
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
device?

This idea was proposed by my colleague Amitawa Biswas in 2005; he is
currently
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
which
cannot be recognized by a PDA is L = {a^n b^n c^n}. To recognize this
language
in a new device, we first get into an "a" state in which, upon seeing an
"a"
symbol, we push this symbol into the bag; upon seeing "b", we get into a
"b"
state in which, upon seeing every "b" symbol, we pop an "a" and push a
"b";
upon seeing a symbol "c", we get into a "c" state in which, upon seeing
a
symbol "c", we pop a symbol from a bag and, if the popped symbol is "b",
we
continue. We accept the word if we are in the final state "c" and the
bag is
empty.

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
not
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

Vladik