Re: is {ww^Rw | w in {0,1}*} context free?

In article <nNqvh.143798$fh6.139331@xxxxxxxxxxxx>,
rabbits77 <rabbits77@xxxxxxxxxxxxxx> wrote:

I say yes...
I can think of a PDA that accepts this language as the following:
Put all the symbols in w onto the stack, non-deterministically check to
see if we have the reverse string by popping them off the stack.
If we reach an empty stack state then check the rest of the string to
see if it is in w.
Am I correct?

No. Instead of "is in w" that should be "is w". You cannot do that
test, because you've already thrown away the entire stack while popping
it to check w^R.

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------
.

Relevant Pages

  • Re: Reverse Forth?
    ... The thing I dislike most is the way the arguments come before the operations and the use of various stack operation like 'dup' and 'swap' and especially 'rot'. ... Instead of building up the stack with each value we read as executing the code, we execute the code by popping values off the stack until the stack is empty. ... we could have the word GET pop the next value from the top of the calling procedure and put it on the current stack. ...
    (comp.lang.misc)
  • Re: DEFCON 16 and Hacking OpenVMS
    ... stack from TGV or Wollongong. ... especially considering they're still popping up (mind ...
    (comp.os.vms)
  • Reverse Forth?
    ... I propose that the stack work differently. ... Once it is empty we've reached the end of the ... stack of the calling procedure for input. ... the procedure simply by popping everything from the stack and pushing it ...
    (comp.lang.misc)
  • Re: Reverse Forth?
    ... The thing I dislike most is the way the arguments come before the operations and the use of various stack operation like 'dup' and 'swap' and especially 'rot'. ... Instead of building up the stack with each value we read as executing the code, we execute the code by popping values off the stack until the stack is empty. ... we could have the word GET pop the next value from the top of the calling procedure and put it on the current stack. ...
    (comp.lang.misc)
  • Please help me understand why these procedures use exch when first called
    ... /Arg1 exch def ... open file "FileName" (file descriptor is now on operand stack) ... convert to string print thus popping ... is call the exch operator on the operands of the stack. ...
    (comp.lang.postscript)