## operation of PDA!!!

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

evinda
Posts: 32
Joined: Fri May 03, 2013 10:16 pm UTC

### operation of PDA!!!

Hi!!! I want to describe the operation of the PDA for the language {w in {0,1}*: w=0^i 1^j, i != j}.
What I have done so far is:
For each 0 that is read we push this onto the stack. Then for each 1 that is read, we pop a 0 from the stack.
But how can I be sure that the number of 0 is not equal to the number of 1? Is my description correct so far? How can I continue?

Sizik
Posts: 1261
Joined: Wed Aug 27, 2008 3:48 am UTC

### Re: operation of PDA!!!

Well, there's three possible cases: i < j, i = j, or i > j. How would you check for each of these individually?
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: operation of PDA!!!

evinda wrote:For each 0 that is read we push this onto the stack. Then for each 1 that is read, we pop a 0 from the stack.

I'd think carefully about this. What do you get if you pop from an empty stack? I think that you'll need two cases.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.