5
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Could you give a more precise description of how this automaton works? $\endgroup$
    – David Richerby
    Commented Mar 27, 2014 at 15:34
  • $\begingroup$ Sure. FAB (Finite Automata Bowl) = A bowl functions similar to a stack, except we give up the temporal order of the stack symbols. We can remove any symbol instead of being restricted to only removing the top symbol of the stack. We can not distinguish whether we first put it the symbol A and then afterward the symbol B, or whether we first put the symbol B and then the symbol A. $\endgroup$
    – Jackie
    Commented Mar 27, 2014 at 16:58
  • 1
    $\begingroup$ Well I guess this model will not accept any CF language that the order of the symbols is important... like palindromes ... $\endgroup$
    – Jackie
    Commented Mar 27, 2014 at 18:51
  • 1
    $\begingroup$ It does recognize all CF languages, and much more. The order in the stack is actually a restrictive constraint. $\endgroup$
    – babou
    Commented Mar 30, 2014 at 21:02
  • 2
    $\begingroup$ Where did you find this automaton? Please give a reference, and/or a full formal (!) definition of the concept. For instance, can "we" choose the symbol to be removed, is it non-deterministic, ...? $\endgroup$
    – Raphael
    Commented Mar 31, 2014 at 7:59

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't quite fully understand. If a bowl automaton is just a counter machine, then it shouldn't be able to accept all CF languages. How would it accept $\{w w^R | w \in \Sigma^* \}$? ($w^R$ is $w$ reversed.) $\endgroup$
    – Joey Eremondi
    Commented Mar 30, 2014 at 22:11
  • 1
    $\begingroup$ It is just a counter machnie, but with several counters, one per bowl symbol. And 2 counters are enough to simulate a Turing machine. The trick is that the stack is mimicked by a single integer in unary notation. Try to read the proof .. then ask again if something is not clear. But look at step 2 of the proof in wikipedia. - - - It is a nice encoding proof. $\endgroup$
    – babou
    Commented Mar 30, 2014 at 22:16
  • $\begingroup$ Riiight, I forgot that a 2-counter machine was Turing Complete. I was getting them confused with Reversal-bounded counter machines, which I've done a bunch of research on. $\endgroup$
    – Joey Eremondi
    Commented Mar 30, 2014 at 22:34
0
$\begingroup$

In your question it sounds like you have a stack but are allowed to see all of it at once and pop at any level, but your comment says order can't be distinguished at all. Going with the second characterization: as Jackie said, a FAB can't recognize any context-free language for which order matters.

Either way, I think an FAB can also recognize the non context-free language of strings with the same number of a's b's and c's. It could just store the whole string and then pop one a, then one b, then one c, in a cycle, accepting if the whole "stack" can be matched up in this way or rejecting if some cycle can't be completed because there is too many of some symbol.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.