Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA).

We can view a nondeterministic transition as a guess; for example if $L = \{x x^R \}$ then an NPDA can guess the middle of the string and correctly recognize $L$.

But this kind of guess "cosumes the stack resource", and the NPDA cannot use it to "accomplish another task" in parallel, so it fails recognizing:

$L = \{ xy \in \{0,1\}^* \mid |x| = |y| \text{ and } x,y \text{ contain the same number of 1s}\} $

I'm wondering if this type of approach to NPDAs has ever been considered and studied ?
In particular does there exist a "classification" of "structural properties" (invented term) of a CFL language that require a guess and/or an "exclusive use" of the stack.

  • 1
    $\begingroup$ 1) The "guess" for the middle does not consume the "stack resource", checking the two parts for equivalence does. 2) There is a body of work on automata using monoids for storage (valence automata); they may have terminology for this. (I know nothing more than these things have been studied, so I can't say if it's a useful pointer.) $\endgroup$ – Raphael May 19 '15 at 10:25
  • $\begingroup$ @Raphael: thanks, I'll give a look at valence automata. BTW I say that "guess" the middle consumes the stack resource, because the stack resource must be used to match (the number of elements of) the left part and (the number of elements of) the right part (that are guessed). I agree that the guess itself doesn't use the stack, but in this case the guessing is not separated from the counting. $\endgroup$ – Vor May 19 '15 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.