[FOM] finite automata equipped with bags:

[Marcin Mostowski]

A propos the problem of FA with a bag 

Kreinovich, Vladik napisał(a):
> 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?

Your definition is not very precise.
Assuming that we can check whether the bag contains a given character,
we can simulate behaviour of arbitrary RAM program, therefore also arbitrary 
Turing machine.
Notice also that you do not need nondeterminism, empty moves are sufficient.
By the way empty moves are also necessary for simulation of Turing machines
on two stack FAs. 

The argument follows: 

Consider a FA with a bag and bag alphabet A = {a1, a2, ..., an}.
At each step a state of the bag can be described as n-tuple
(a1^{k_1}, ..., an^{k_n}).
This n-tuple codes n-tuple of natural numbers
(k_1, ..., k_n). 

Take a RAM program P = (P1, P2, ..., Pm) consisting of instructions of the 
form
(1) ri := 0,
(2) ri := rj,
(3) ri := ri + 1,
(4) if ri=0 then goto t, for t between 1 and m+1.
The numbers i,j are between 1 and n. 

Take the states s1, s2, ..., sm corresponding to (P1, P2, ..., Pm) and some 
additional.
A state si and a tuple (k_1, ..., k_n) describes a configuration of the 
program P. 

Now we have to simulate the behaviour of P.
Instructions (1)-(3) can be simulated in an obvious way.
For instruction (4) being in a state sw we check whether ai belongs to the 
bag,
if it is not so then not moving the head we change the state from sw to st,
otherwise change the state from sw to s{w+1}. 

Then havin any RAM program P we define FA with a bag computing the same as 
follows:
Firstly scan the input coding it in r1, then carry out the simulation of P,
if the result is accepting then finish in an accepting state. 

Marcin Mostowski 


_____________________ 

Marcin Mostowski
Department of Logic
Institute of Philosophy
Warsaw University