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!!!

Postby evinda » Tue Jan 14, 2014 10:14 pm UTC

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?

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

Re: operation of PDA!!!

Postby Sizik » Wed Jan 15, 2014 2:12 am UTC

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.

User avatar
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!!!

Postby jestingrabbit » Mon Jan 27, 2014 10:54 am UTC

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.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 5 guests