patternMinor
What is Finite Automata Bowl?
Viewed 0 times
finiteautomatawhatbowl
Problem
I was trying to find info about this Finite Automata type FAB (Finite Automata Bowl) and wasn't able to find a lot. It is basically the rules that apply to PDA apply to FAB except you drop the temporal order of the stack. So instead of being restricted to only removing the top symbol of the stack, you can remove any symbol of the bowl.
The question is, does there exist a context-free language that is not accepted by an FAB?
The question is, does there exist a context-free language that is not accepted by an FAB?
Solution
If I understand the rules correctly ...
First I call them here Bowl Automata, since they cannot be considered
finite because of the Bowl.
All you can do with the bowl symbols is to count, with a different
count for each symbol.
So the bowl automaton is only a multicounter automaton, which has been
analyzed a long time ago as counter machine, with many variants.
There seems to be significant literature about it.
Counter machines with 2 counters (i.e. 2 bowl symbols) are actually as
powerful as Turing machines (TM), up to proper initial encoding of the
problem ... which is a significant constraint. Read the proof in
Wikipedia. But this constraint is apparently only when the input of the
TM is to be encoded in the counters. This result appears in a 1967
book by Minsky, Computation. For off-line TM, taking their input on
a separate tape, there is no such problem.
So all recursively enumerable languages can be recognized by a two symbol Bowl Automaton, including of course the CF languages. The simpler case of the PDA is worth examining, as it is an important step of the general proof.
The PushDown Automaton is an off-line machine since the
input is from a normal read-only tape. The encoding suggested in the proof (step 2 of
the proof) TM allows it to simulate a PDA with only two bowl
symbols. The gist of the construction is to consider the PDA stack as
representing a number in base $n$, where $n$ is the cardinality of the
stack alphabet. Instead, you use one bowl symbol to represent the
stack number in unary notation (just use a very big bowl). Actually,
you simplify by first using a stack with only two symbols, to use
binary notation before making it unary in the bowl. The remaining
bowl symbol is used for book-keeping while simulating the binary stack with unary notation. Read it from wikipedia, it is
quite simple.
So each CF language is accepted by some Bowl Automaton, actually even restricted to two bowl symbols (but a very large number of each :-)
The construction is simpler for the simulation of a PDA stack. But since a TM can be simulated with two stacks and a finite control, a TM can be simulated by a Bowl Automaton. An the four counters (2 for each stack) can actually be reduced to two.
First I call them here Bowl Automata, since they cannot be considered
finite because of the Bowl.
All you can do with the bowl symbols is to count, with a different
count for each symbol.
So the bowl automaton is only a multicounter automaton, which has been
analyzed a long time ago as counter machine, with many variants.
There seems to be significant literature about it.
Counter machines with 2 counters (i.e. 2 bowl symbols) are actually as
powerful as Turing machines (TM), up to proper initial encoding of the
problem ... which is a significant constraint. Read the proof in
Wikipedia. But this constraint is apparently only when the input of the
TM is to be encoded in the counters. This result appears in a 1967
book by Minsky, Computation. For off-line TM, taking their input on
a separate tape, there is no such problem.
So all recursively enumerable languages can be recognized by a two symbol Bowl Automaton, including of course the CF languages. The simpler case of the PDA is worth examining, as it is an important step of the general proof.
The PushDown Automaton is an off-line machine since the
input is from a normal read-only tape. The encoding suggested in the proof (step 2 of
the proof) TM allows it to simulate a PDA with only two bowl
symbols. The gist of the construction is to consider the PDA stack as
representing a number in base $n$, where $n$ is the cardinality of the
stack alphabet. Instead, you use one bowl symbol to represent the
stack number in unary notation (just use a very big bowl). Actually,
you simplify by first using a stack with only two symbols, to use
binary notation before making it unary in the bowl. The remaining
bowl symbol is used for book-keeping while simulating the binary stack with unary notation. Read it from wikipedia, it is
quite simple.
So each CF language is accepted by some Bowl Automaton, actually even restricted to two bowl symbols (but a very large number of each :-)
The construction is simpler for the simulation of a PDA stack. But since a TM can be simulated with two stacks and a finite control, a TM can be simulated by a Bowl Automaton. An the four counters (2 for each stack) can actually be reduced to two.
Context
StackExchange Computer Science Q#23128, answer score: 4
Revisions (0)
No revisions yet.